Abstract
The supereulerian graph problem, raised by Boesch et al. (J Graph Theory 1:79–84, 1977), asks when a graph has a spanning eulerian subgraph. Pulleyblank showed that such a decision problem, even when restricted to planar graphs, is NP-complete. Jaeger and Catlin independently showed that every 4-edge-connected graph has a spanning eulerian subgraph. In 1992, Zhan showed that every 3-edge-connected, essentially 7-edge-connected graph has a spanning eulerian subgraph. It was conjectured in 1995 that every 3-edge-connected, essentially 5-edge-connected graph has a spanning eulerian subgraph. In this paper, we show that if G is a 3-edge-connected, essentially 4-edge-connected graph and if for every pair of adjacent vertices u and v, d G (u) + d G (v) ≥ 9, then G has a spanning eulerian subgraph.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Boesch F.T., Suffel C., Tindell R.: The spanning subgraphs of eulerian graphs. J. Graph Theory 1, 79–84 (1977)
Bondy J.A., Murty U.S.R.: Graph Theory with Applications. Macmillan, London and Elsevier, New York (1976)
Catlin P.A.: A reduction method to find spanning eulerian subgraphs. J. Graph Theory 12, 29–45 (1988)
Catlin P.A.: Supereulerian graphs, a survey. J. Graph Theory 16, 177–196 (1992)
Catlin P.A., Han Z., Lai H.-J.: Graphs without spanning eulerian subgraphs. Discrete Math. 160, 81–91 (1996)
Chen, Z.H., Lai, H.-J.: Reduction techniques for super-Eulerian graphs and related topics (a survey), Combinatorics and Graph Theory 95, vol. 1 (Hefei), pp. 53–69, World Sci. Publishing, River Edge (1995)
Jaeger F.: A note on subeulerian graphs. J. Graph Theory 3, 91–93 (1979)
Lai, H.-J.: Yehong Shao, Gexin Yu and Mingquan Zhan, Hamiltonian connectedness in 3-connected line graphs, Discret. Appl. Math. (accepted)
Pulleyblank W.R.: A note on graphs spanned by eulerian graphs. J. Graph Theory 3, 309–310 (1979)
Ryjác̆ek Z.: On a closure concept in claw-free graphs. J. Combin. Theory Ser. B 70, 217–224 (1997)
Shao, Y.: Claw-free Graphs and Line Graphs, Ph. D. Dissertation, West Virginia University (2005)
Thomassen C.: Reflections on graph theory. J. Graph Theory 10, 309–324 (1986)
Zhan S.: On Hamiltonian line graphs and connectivity. Discret. Math. 89, 89–95 (1991)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research is supported by the Millersville University Faculty Released-Time grant.
Rights and permissions
About this article
Cite this article
Lai, HJ., Li, H., Shao, Y. et al. On 3-Edge-Connected Supereulerian Graphs. Graphs and Combinatorics 27, 207–214 (2011). https://doi.org/10.1007/s00373-010-0974-1
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-010-0974-1