THREE-CYCLE REVERSIONS IN ORIENTED PLANAR TRIANGULATIONS
スポンサーリンク
概要
- 論文の詳細を見る
"A planar triangulation ＄G＄ is a simple graph embedded in the plane so that each face of ＄G＄ is triangular and that any two faces share at most one edge. A ＄(*)＄ -orientation ＄D^{*}(G)＄ of ＄G＄ is an orientation of ＄G＄ such that the outdegree of each vertex on ＄￥partial G＄ is 1 and that of each vertex not on ＄￥partial G＄ is 3, where ＄￥partial G＄ denotes the outer 3-cycle of ＄G＄ . In this paper, we shall show that for any planar triangulation ＄G＄ , there exists at least one (*)-orientation and that any two ＄t*＄ )＄-＄ orientations of ＄G＄ can be transformed into each other by a sequenoe of 3-cycle reversions, where the S-cycle reversion is a transformation in an oriented graph which replaces an oriented 3-cycle with the one with the inverse orientation. Finally, we shall show that in order to transform two (*)-orientations of ＄G＄ , we need at most ＄￥lfloor￥frac{1}{2}n^{2}-5n+￥frac{27}{2}￥rfloor＄ 3-cycle reversions, where ＄n=|V(G)|＄ . The order of our estimation cannot be improved."
- Yokohama City University and Yokohama National Universityの論文
- 1997-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