Cyclically five-connected cubic graphs
Cyclically five-connected cubic graphs
复制标题
循环五连通立方图
DOI：
10.1016/j.jctb.2017.03.003
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Thomas, Robin
中科院分区：
文献类型：
--
作者：
Robertson, Neil;Seymour, P.D.;Thomas, Robin
一个三次图G是循环5-连通的，如果G是简单的，3-连通的，至少有10个顶点，并且对于每一个不超过4条边的集合F，G\F的至多一个分支包含回路。证明了：如果G和H是循环5连通三次图，且H拓扑包含G，则G和H同构，或存在一个循环5连通三次图G′，使得H拓扑包含G′，且G′由G以下列两种方式之一得到.或者G′是通过细分G的两条不同的边并用一条边连接这两个新的顶点而从G得到的，或者G′是通过细分一个长度为5的回路的每条边并通过匹配到一个与G不相交的长度为5的新回路来连接这两个新的顶点而从G得到的，使得这两个回路的循环阶一致。我们证明了一个同伴的结果，通过稍微增加H的连接，我们能够消除第二个建设。我们还证明了这两个结果的版本时，G几乎是循环5-连接的意义上，它满足的定义，除了4-边切割，使一边是一个电路的长度为4。在这种情况下，要求G′几乎是循环5-连通的，并且长度为4的回路比G少。特别地，如果G最多有一个长度为4的回路，则G′必须是循环5-连通的。然而，在这种更一般的设置中，描述可能的图G′的运算更加复杂。
A cubic graph G is cyclically 5-connected if G is simple, 3-connected, has at least 10 vertices and for every set F of edges of size at most four, at most one component of G\F contains circuits. We prove that if G and H are cyclically 5-connected cubic graphs and H topologically contains G, then either G and H are isomorphic, or (modulo well-described exceptions) there exists a cyclically 5-connected cubic graph G′ such that H topologically contains G′ and G′ is obtained from G in one of the following two ways. Either G′ is obtained from G by subdividing two distinct edges of G and joining the two new vertices by an edge, or G′ is obtained from G by subdividing each edge of a circuit of length five and joining the new vertices by a matching to a new circuit of length five disjoint from G in such a way that the cyclic orders of the two circuits agree. We prove a companion result, where by slightly increasing the connectivity of H we are able to eliminate the second construction. We also prove versions of both of these results when G is almost cyclically 5-connected in the sense that it satisfies the definition except for 4-edge cuts such that one side is a circuit of length four. In this case G′ is required to be almost cyclically 5-connected and to have fewer circuits of length four than G. In particular, if G has at most one circuit of length four, then G′ is required to be cyclically 5-connected. However, in this more general setting the operations describing the possible graphs G′ are more complicated.
三次图中的均匀循环边连通性
DOI：
--
发表时间：
1991
期刊：
Comb.
影响因子：
--
作者：
R. Aldred;D. Holton;B. Jackson
通讯作者：
B. Jackson
循环 k 连接立方图中的边缩减
DOI：
--
发表时间：
1992
期刊：
J. Comb. Theory B
影响因子：
--
作者：
W. McCuaig
通讯作者：
W. McCuaig
DOI：
--
发表时间：
1990
期刊：
J. Comb. Theory B
影响因子：
--
作者：
N. Robertson;P. Seymour
通讯作者：
P. Seymour