1. The Minimum Number of Dependent Arcs in….
- Author
-
Fengwei Xu, Weifan Wang, and Ko-Wei Lih
- Subjects
- *
GRAPH theory , *PATHS & cycles in graph theory , *LINEAR dependence (Mathematics) , *COMBINATORICS , *MATHEMATICAL analysis , *IMAGE analysis - Abstract
Let D be an acyclic orientation of a simple graph G. An arc is called dependent if its reversal creates a directed cycle. Let d(D) denote the number of dependent arcs in D. Define dmin(G) to be the minimum number of d(D) over all acyclic orientations D of G. Let Cn denote the cycle on n vertices. The cube Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed. is the graph defined on the same vertex set of Cn such that any two distinct vertices u and v are adjacent in Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed. if and only if their distance in Cn is at most 3. In this paper, we study the structure of Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed. to determine its minimum number of dependent arcs. [ABSTRACT FROM AUTHOR]
- Published
- 2011