Long cycles and spanning subgraphs of locally maximal 1‐planar graphs
Long cycles and spanning subgraphs of locally maximal 1‐planar graphs
复制标题
局部最大 1â平面图的长循环和跨越子图
DOI：
10.1002/jgt.22542
复制
发表时间：
2020
影响因子：
0.9
通讯作者：
Carol T. Zamfirescu
中科院分区：
文献类型：
--
作者：
Igor Fabrici;Jochen Harant;Tomáš Madaras;Samuel Mohr;Roman Soták;Carol T. Zamfirescu
一个图形是1‐平面的，如果它在平面上有一个绘图，使得每条边最多被另一条边交叉一次。此外，如果这幅图具有附加的性质，即对于两条边的每次交叉，这些边的端点会产生一个完整的子图，那么这个图在局部是最大平面的。对于一个3连通的局部极大1平面图g，我们证明了生成3连通平面子图g的存在性，并证明了gis的哈密顿函数g最多有3个3顶点切割，gis的可跟踪函数g最多有4个3顶点切割。此外，还给出了无穷多个不可追溯的5连通1平面图。
A graph is 1‐planarif it has a drawing in the plane such that each edge is crossed at most once by another edge. Moreover, if this drawing has the additional property that for each crossing of two edges the end vertices of these edges induce a complete subgraph, then the graph islocally maximal1‐planar. For a 3‐connected locally maximal 1‐planar graphG, we show the existence of a spanning 3‐connected planar subgraph and prove thatGis Hamiltonian ifGhas at most three 3‐vertex‐cuts, and thatGis traceable ifGhas at most four 3‐vertex‐cuts. Moreover, infinitely many nontraceable 5‐connected 1‐planar graphs are presented.
登录
查看更多内容
DOI：
--
发表时间：
1973
期刊：
Journal of Combinatorial Theory
影响因子：
--
作者：
B. Grünbaum;H. Walther
通讯作者：
H. Walther
很少有 3 割的多面体是哈密顿量
影响因子：
0.7
作者：
G. Brinkmann;C. Zamfirescu
通讯作者：
C. Zamfirescu
多面体上的简单路径。
影响因子：
0.6
作者：
J. Moon;L. Moser
通讯作者：
L. Moser
独特的可嵌入平面图
影响因子：
0.8
作者：
H. Fleischner
通讯作者：
H. Fleischner
3 连通图中有界度的 2 连通覆盖
影响因子：
0.9
作者：
Zhicheng Gao
通讯作者：
Zhicheng Gao