The Matching Extendability of Optimal 1-Planar Graphs
The Matching Extendability of Optimal 1-Planar Graphs
复制标题
最优一平面图的匹配可扩展性
DOI：
10.1007/s00373-018-1932-6
复制
发表时间：
2018
影响因子：
0.7
通讯作者：
Suzuki Yusuke
中科院分区：
文献类型：
--
作者：
Fujisawa Jun;Segawa Keita;Suzuki Yusuke
一个图G称为1-平面图，如果它可以画在球面或平面上，使得G的任何边与另一条边至多有一个交点。此外，G称为最优1-平面图，如果。本文研究了最优1-平面图的匹配可扩性。证明了偶数阶的最优1-平面图G是2-可扩的，除非G中有一个4-圈C将其分成两个奇数分支。此外，对任意5-连通最优1-平面图，我们刻画了一个不可扩的三边匹配。
A graphGis said to be1-planarif it can be drawn on the sphere or plane so that any edge ofGhas at most one crossing point with another edge. Moreover,Gis called anoptimal1-planar graph if. In this paper, we investigate the matching extendability of optimal 1-planar graphs. It is shown that every optimal 1-planar graphGof even order is 2-extendable unlessGcontains a 4-cycleCwhich separates the graph into two odd components. Moreover, for any 5-connected optimal 1-planar graph, we characterize a matching with three edges which is not extendable.