zbMATH — the first resource for mathematics

On 3-edge-connected supereulerian graphs. (English) Zbl 1235.05084
Summary: The supereulerian graph problem, raised by F.T. Boesch, C. Suffel, and R. Tindell [“The spanning subgraphs of Eulerian graphs”, J. Graph Theory 1, 79–84 (1977; Zbl 0363.05042)], 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) \geq 9$$, then $$G$$ has a spanning eulerian subgraph.
MSC:
 05C45 Eulerian and Hamiltonian graphs 05C40 Connectivity
Full Text:
References:
 [1] Boesch F.T., Suffel C., Tindell R.: The spanning subgraphs of eulerian graphs. J. Graph Theory 1, 79–84 (1977) · Zbl 0363.05042 · doi:10.1002/jgt.3190010115 [2] Bondy J.A., Murty U.S.R.: Graph Theory with Applications. Macmillan, London and Elsevier, New York (1976) [3] Catlin P.A.: A reduction method to find spanning eulerian subgraphs. J. Graph Theory 12, 29–45 (1988) · Zbl 0659.05073 · doi:10.1002/jgt.3190120105 [4] Catlin P.A.: Supereulerian graphs, a survey. J. Graph Theory 16, 177–196 (1992) · Zbl 0771.05059 · doi:10.1002/jgt.3190160209 [5] Catlin P.A., Han Z., Lai H.-J.: Graphs without spanning eulerian subgraphs. Discrete Math. 160, 81–91 (1996) · Zbl 0859.05060 · doi:10.1016/S0012-365X(95)00149-Q [6] 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) [7] Jaeger F.: A note on subeulerian graphs. J. Graph Theory 3, 91–93 (1979) · Zbl 0396.05034 · doi:10.1002/jgt.3190030110 [8] Lai, H.-J.: Yehong Shao, Gexin Yu and Mingquan Zhan, Hamiltonian connectedness in 3-connected line graphs, Discret. Appl. Math. (accepted) [9] Pulleyblank W.R.: A note on graphs spanned by eulerian graphs. J. Graph Theory 3, 309–310 (1979) · Zbl 0414.05040 · doi:10.1002/jgt.3190030316 [10] Ryjácek Z.: On a closure concept in claw-free graphs. J. Combin. Theory Ser. B 70, 217–224 (1997) · Zbl 0872.05032 · doi:10.1006/jctb.1996.1732 [11] Shao, Y.: Claw-free Graphs and Line Graphs, Ph. D. Dissertation, West Virginia University (2005) [12] Thomassen C.: Reflections on graph theory. J. Graph Theory 10, 309–324 (1986) · Zbl 0614.05050 · doi:10.1002/jgt.3190100308 [13] Zhan S.: On Hamiltonian line graphs and connectivity. Discret. Math. 89, 89–95 (1991) · Zbl 0727.05037 · doi:10.1016/0012-365X(91)90401-M
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.