Collapsible subgraphs of a 4-edge-connected graph
Collapsible subgraphs of a 4-edge-connected graph
复制标题
4 边连通图的可折叠子图
DOI：
10.1016/j.dam.2019.01.033
复制
发表时间：
2019
影响因子：
1.1
通讯作者：
Meng Zhang
中科院分区：
文献类型：
--
作者：
Ran Gu;Hong-Jian Lai;Yanting Liang;Zhengke Miao;Meng Zhang
Jaeger在1979年证明了每一个4-边连通图都是超欧拉图，即有生成欧拉子图的图。卡特林在1988年通过证明每一个4-边连通图都是可折叠的，是超欧拉图的可收缩配置的图，从而使耶格的结果更加尖锐。为了进一步研究4-边连通图的可折叠子图，在Catlin et al.（2009），证明了每个4-边连通图在去掉任意两条边后仍然是可折叠的。我们证明了以下几点：·[(i)]每个4-边连通的G包含两个顶点x，y使得x和y中的一个在G中具有最小度，并且G-x和G-y都是可折叠的。[（ii）]设G是4-边连通图，X ∈ E（G）是边子集，|X| ≤ 3。则G-X是可折叠的当且仅当X不包含在G的4-边割中。·[（iii）]设G是一个4-边连通图，X ∈ E（G）是一个边子集，|X| ≤ 4。则G-X是可塌缩的当且仅当G-X不可压缩到{K2 c，K2，K2，2，K2，3，K2，4}中的成员。这些结果推广了Jaeger（1979）和Catlin（1988）的结果。
Jaeger in 1979 showed that every 4-edge-connected graph is supereulerian, graphs that have spanning eulerian subgraphs. Catlin in 1988 sharpened Jaeger’s result by showing that every 4-edge-connected graph is collapsible, graphs that are contractible configurations of supereulerian graphs. To further study collapsible subgraphs of a 4-edge-connected graph, in Catlin et al.(2009), it is shown that every 4-edge-connected graph remains collapsible after removing any two edges. We prove the following.•[(i)] Every 4-edge-connected G contains two vertices x, y such that one of x and y has minimum degree in G and both G− x and G− y are collapsible.•[(ii)] Let G be a 4-edge-connected graph and let X⊂ E (G) be an edge subset with| X|≤ 3. Then G− X is collapsible if and only if X is not contained in a 4-edge-cut of G.•[(iii)] Let G be a 4-edge-connected graph and let X⊂ E (G) be an edge subset with| X|≤ 4. Then G− X is collapsible if and only if G− X is not contractible to a member in {K 2 c, K 2, K 2, 2, K 2, 3, K 2, 4}. These extend former results of Jaeger (1979) and Catlin (1988).