Tutte paths and long cycles in circuit graphs
Tutte paths and long cycles in circuit graphs
复制标题
电路图中的 Tutte 路径和长周期
DOI：
10.1016/j.jctb.2022.07.006
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Yu, Xingxing
中科院分区：
文献类型：
--
作者：
Wigal, Michael C.;Yu, Xingxing
通过证明每个2-连通平面图G在任意两个给定顶点之间包含一条Tutte路P，即G− P的每个分支在P上至多有三个邻域，证明了4-连通平面图是汉密尔顿连通的.本文对包含所有3-连通平面图的自然类--回路图，证明了这一结果的一个定量版本，通过进一步控制G− P中的分支数，我们还给出了这个结果的一个应用，即给出了本质4连通平面图的周长的一个最佳可能界.
Thomassen proved that 4-connected planar graphs are Hamilton connected by showing that every 2-connected planar graph G contains a Tutte path P between any two given vertices, that is, every component of G− P has at most three neighbors on P. In this paper, we prove a quantitative version of this result for circuit graphs, a natural class of planar graphs which includes all 3-connected planar graphs, by further controlling the number of components in G− P. We also give an application of this result by providing a best possible bound for the circumference of essentially 4-connected planar graphs.
登录
查看更多内容
基本上 4 连通平面三角剖分的周长
DOI：
--
发表时间：
2021
期刊：
J. Graph Algorithms Appl.
影响因子：
--
作者：
Igor Fabrici;J. Harant;Samuel Mohr;Jens M. Schmidt
通讯作者：
Jens M. Schmidt
三连通平面图中的最长循环
DOI：
--
发表时间：
1992
期刊：
J. Comb. Theory B
影响因子：
--
作者：
B. Jackson;N. Wormald
通讯作者：
N. Wormald
不相交的路径、平坦化循环和跨越行走
DOI：
--
发表时间：
1997
期刊：
影响因子：
--
作者：
Xingxing Yu
通讯作者：
Xingxing Yu
4 连通射影平面图是哈密顿图
DOI：
--
发表时间：
1994
期刊：
J. Comb. Theory B
影响因子：
--
作者：
R. Thomas;Xingxing Yu
通讯作者：
Xingxing Yu
四、列表拓扑
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
Tait
通讯作者：
Tait