ON THE FLIP OPERATIONS OF CLIQUE-ACYCLIC ORIENTATIONS OF GRAPHS
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we study the edge flip operations on some classes of clique-acyclic digraphs (that is, digraphs containing no directed triangle), especially we show that if ＄G＄ is a simple undirected graph whose every induced subgraph has a vertex ＄v＄ whose degree ＄5(v)￥leqq 7＄, any two clique-acyclic orientations ＄￥pi＄ and ＄￥pi^{￥prime}＄ have a sequence of clique-acyclic orientations ＄￥pi=￥pi 0,＄ ＄￥pi_{1},＄ ＄￥ldots＄ , ＄￥pi￥iota=￥pi^{￥prime}＄ such that we obtain ＄￥pi＄, by reversing the orientation of one single edge of ＄￥pi_{i-1}＄ , (then we call that ＄￥pi＄' is attainable from ＄￥pi＄). The latter bound "＄￥delta(G)￥leqq 7＄'' is sharp. Actually, if ＄G＄ is a connected 8-regular graph, then there are exactly five examples of ＄G＄ each of which has a clique-acyclic orientation such that, if we flip any edge of it, the resulting new orientation has a directed triangle. Last, we show that, except for the above five examples of ＄G＄ , any two clique-acyclic orientations of a connected graph ＄G＄ whose maximum degree ＄￥Delta(G)￥leqq 8＄ , are attainable from one to another.
- Yokohama City University and Yokohama National Universityの論文
- 1999-00-00
Yokohama City University and Yokohama National University | 論文
- UNIVERSAL SPACES FOR ZERO-DIMENSIONAL CLOSED IMAGES OF METRIC SPACES : dedicate to my mother on her 77th birthday
- A TOPOLOGICAL APPROACH TO THE NIELSEN'S REALIZATION PROBLEM FOR HAKEN 3-MANIFOLDS
- ON A CERTAIN CLASS OF FUNCTIONS OF BOUNDED BOUNDARY ROTATION
- ON THE SWITCHBACK VERTION OF JOSEPHUS PROBLEM
- ON EXISTENCE OF SOLUTIONS FOR THE UNILATERAL PROBLEM ASSOCIATED TO THE DEGENERATE KIRCHHOFF EQUATIONS