Y‐rotation in k‐minimal quadrangulations on the projective plane
Y‐rotation in k‐minimal quadrangulations on the projective plane
复制标题
DOI：
10.1002/jgt.20583
复制
发表时间：
2012-03
影响因子：
0.9
通讯作者：
Atsuhiro Nakamoto;Yusuke Suzuki
中科院分区：
文献类型：
--
作者：
Atsuhiro Nakamoto;Yusuke Suzuki
设G是曲面上的四边形剖分，f是由4圈abcd包围的面。f的面收缩是识别a和c（或B和d）以消除f。我们说曲面上的简单四边形图G是k-极小的，如果最短本质圈的长度是k（≥3），但是G中的任何面收缩都破坏了这个性质或图的简单性。在这篇文章中，我们将证明，对于任何固定整数k≥3，射影平面上的任何两个k-极小四边形可以通过一系列3次顶点的Y-旋转相互转换，其中3次顶点v的Y-旋转是在由三个四边形面vv 1v 2 v3，vv 3v 4v 5和vv 5v 6v 1组成的六边形区域中移除三条边vv 1，vv 3，vv 5，并添加三个边Vv 2、Vv 4、Vv 6。实际上，每一个k-极小四边形（k≥4）都可以通过莫比乌斯收缩（英语：Möbius constraction）的运算约化为一个（k-1）-极小四边形，这在引理13中有提到。© 2011 Wiley Periodicals，Inc. J Graph Theory 69：301-313，2012
Let G be a quadrangulation on a surface, and let f be a face bounded by a 4‐cycle abcd. A face‐contraction of f is to identify a and c (or b and d) to eliminate f. We say that a simple quadrangulation G on the surface is k‐minimal if the length of a shortest essential cycle is k(≥3), but any face‐contraction in G breaks this property or the simplicity of the graph. In this article, we shall prove that for any fixed integer k≥3, any two k‐minimal quadrangulations on the projective plane can be transformed into each other by a sequence of Y‐rotations of vertices of degree 3, where a Y‐rotation of a vertex v of degree 3 is to remove three edges vv1, vv3, vv5 in the hexagonal region consisting of three quadrilateral faces vv1v2v3, vv3v4v5, and vv5v6v1, and to add three edges vv2, vv4, vv6. Actually, every k‐minimal quadrangulation (k≥4) can be reduced to a (k−1)‐minimal quadrangulation by the operation called Möbius contraction, which is mentioned in Lemma 13. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 301–313, 2012