rapid-communication

Collapsible subgraphs of a 4-edge-connected graph

Authors:

Meng ZhangAuthors Info & Claims

Volume 260, Issue C

Pages 272 - 277

https://doi.org/10.1016/j.dam.2019.01.033

Published: 15 May 2019 Publication History

Abstract

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).

References

[1]

Boesch F.T., Suffel C., Tindell R., The spanning subgraphs of eulerian graphs, J. Graph Theory 1 (1988) 79–84.

[2]

Bondy J.A., Murty U.S.R., Graph Theory, Springer-New York, 2008.

Digital Library

[3]

Catlin P.A., A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–45.

[4]

Catlin P.A., Super-eulerian graphs, a survey, J. Graph Theory 16 (1992) 177–196.

[5]

Catlin P.A., Han Z.-Y., Lai H.-J., Graphs without spanning closed trails, Discrete Math. 160 (1996) 81–91.

[6]

Catlin P.A., Lai H.-J., Shao Y., Edge-connectivity and edge-disjoint spanning trees, Discrete Math. 309 (2009) 1033–1040.

Digital Library

[7]

Chen Z.H., Lai H.-J., Reduction techniques for super-eulerian graphs and related topics - a survey, in: Combinatorics and Graph Theory, Volume 1, World Sci. Publishing, River Edge, NJ, 1995, pp. 53–69.

[8]

Fleischer H., Eine gemeinsame Basis für die Theorie der Eulerschen Graphen und den Satz von Petersen, Monats. Matt. 81 (1976) 267–278.

[9]

Jaeger F., A note on subeulerian graphs, J. Graph Theory 3 (1979) 91–93.

[10]

Lai H.-J., Shao Y., H, Yan an update on supereulerian graphs, WSEAS Trans. Math. 12 (2013) 926–940.

[11]

Li P., Cycles and bases of graphs and matroids, (Ph.D. dissertation) West Virginia University, 2012.

[12]

Li P., Lai H.-J., Liang Y., Characterization of removable elements with respect to having k disjoint bases in a matroid, Discrete Appl. Math. 160 (2012) 2445–2451.

[13]

Li P., Liang Y.T., Xu J., Reinforcing a matroid to have k disjoint bases, Appl. Math. 1 (2010) 244–249.

[14]

Mader W., Edge-connectivity preserving reductions, in: Proceedings of Advances in Graph Theory, North-Holland, 1978.

[15]

Mader W., A reduction method for edge-connectivity in graphs, Ann. Discrete Math. 3 (1978) 145–164.

[16]

Pulleyblank W.R., A note on graphs spanned by eulerian graphs, J. Graph Theory 3 (1979) 309–310.

[17]

R. A, Brualdi comments on bases in dependence structures, Bull. Aust. Math. Sos. 1 (1969) 161–167.

[18]

St. J. A. Nash-Williams C., Edge-disjoint spanning trees of finite graphs, J. Lond. Math. Soc. 36 (1961) 445–450.

[19]

Tutte W.T., On the problem of decomposing a graph into n connected factors, J. Lond. Math. Soc. 36 (1961) 221–230.

Index Terms

Collapsible subgraphs of a 4-edge-connected graph
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation

Index terms have been assigned to the content through auto-classification.

Recommendations

Supereulerian graphs with width s and s -collapsible graphs

For an integer s 0 and for u , v V ( G ) with u v , an ( s ; u , v ) -trail-system of G is a subgraph H consisting of s edge-disjoint ( u , v ) -trails. A graph is supereulerian with width s if for any u , v V ( G ) with u v , G has a spanning ( s ; u , ...
On 3-edge-connected supereulerian graphs in graph family C (l,k)

Let l>0 and k>=0 be two integers. Denote by C(l,k) the family of 2-edge-connected graphs such that a graph G@?C(l,k) if and only if for every bond S@?E(G) with |S|@?3, each component of G-S has order at least (|V(G)|-k)/l. In this paper we prove that if ...
Snarks, Hypohamiltonian Graphs and Non-Supereulerian Graphs

A graph G is hypohamiltonian if it is not Hamiltonian but for each $$v\in V(G)$$vźV(G), the graph $$G-v$$G-v is Hamiltonian. A graph is supereulerian if it has a spanning Eulerian subgraph. A graph G is called collapsible if for every even subset $$R\...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete Applied Mathematics

Discrete Applied Mathematics Volume 260, Issue C

May 2019

294 pages

ISSN:0166-218X

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 15 May 2019

Author Tags

Qualifiers

Rapid-communication

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents