文章詳目資料

Tamsui Oxford Journal of Information and Mathematical Sciences Scopus

  • 加入收藏
  • 下載文章
篇名 The Minimum Number of Dependent Arcs in C
卷期 27:4
作者 Fengwei XuWeifan Wang
頁次 397-410
關鍵字 Acyclic orientationDependent arcCycleCube
出刊日期 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.

相關文獻