篇名 | The Minimum Number of Dependent Arcs in C |
---|---|
卷期 | 27:4 |
作者 | Fengwei Xu 、 Weifan Wang |
頁次 | 397-410 |
關鍵字 | Acyclic orientation 、 Dependent arc 、 Cycle 、 Cube |
出刊日期 | 201111 |
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 C3 n is the graph defined on the same vertex set of Cn such that any two distinct vertices u and v are adjacent in C3 n if and only if their distance in Cn is at most 3. In this paper, we study the structure of C3 3k to determine its minimum number of dependent arcs.