Minor relation for quadrangulations on the projective plane
Minor relation for quadrangulations on the projective plane
复制标题
射影平面上四边形的次关系
DOI：
10.1016/j.dam.2015.07.037
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Yonekura
中科院分区：
文献类型：
--
作者：
N. Matsumoto;A. Nakamoto;S. Yonekura
曲面上的四边形是一个简单图在曲面上的映射，每个面都是四边形。本文证明了对任意射影平面上的二部四边形图G，存在一个射影平面上的二部四边形图序列G= G1，G2，…，Gn，使得（i）Gi + 1是Gi的子式，|G i| − 2≤| G i+ 1| ≤| G i| − 1，对i= 1，.，n− 1，（ii）G n同构于K3，4或K4，4−−，其中K4，4−−是由K4，4消去两条独立边而得到的图。为了证明这个定理，我们使用了两个局部约化，它们将一个四边形Q变换为另一个四边形Q′，其中Q≥ m Q′，1≤| Q| −| Q′| ≤ 2。此外，我们证明了一个类似的结果，非二部四边形的射影平面上。
A quadrangulation on a surface is a map of a simple graph on the surface with each face quadrilateral. In this paper, we prove that for any bipartite quadrangulation G on the projective plane, there exists a sequence of bipartite quadrangulations on the projective plane G= G 1, G 2,…, G n such that (i) G i+ 1 is a minor of G i with| G i|− 2≤| G i+ 1|≤| G i|− 1, for i= 1,…, n− 1,(ii) G n is isomorphic to either K 3, 4 or K 4, 4−−, where K 4, 4−− is the graph obtained from K 4, 4 by deleting two independent edges. In order to prove the theorem, we use two local reductions for quadrangulations which transform a quadrangulation Q into another quadrangulation Q′ with Q≥ m Q′ and 1≤| Q|−| Q′|≤ 2. Moreover, we prove a similar result for non-bipartite quadrangulations on the projective plane.