Supereulerian graphs with small matching number and 2-connected hamiltonian claw-free graphs

Abstract

AbstractMotivated by the Chinese Postman Problem, Boesch, Suffel, and Tindell [The spanning subgraphs of Eulerian graphs, J. Graph Theory 1 (1977), pp. 79–84] proposed the supereulerian graph problem which seeks the characterization of graphs with a spanning Eulerian subgraph. Pulleyblank [A note on graphs spanned by Eulerian graphs, J. Graph Theory 3 (1979), pp. 309–310] showed that the supereulerian problem, even within planar graphs, is NP-complete. In this paper, we settle an open problem raised by An and Xiong on characterization of supereulerian graphs with small matching numbers. A well-known theorem by Chvátal and Erdös [A note on Hamilton circuits, Discrete Math. 2 (1972), pp. 111–135] states that if G satisfies α(G)≤κ(G), then G is hamiltonian. Flandrin and Li in 1989 showed that every 3-connected claw-free graph G with α(G)≤2 κ(G) is hamiltonian. Our characterization is also applied to show that every 2-connected claw-free graph G with α(G)≤3 is hamiltonian, with only one well-characterized exceptional class.Keywords: supereulerian graphscollapsible graphsreductionscontraction characterizations2010 AMS Subject Classifications:: 05C4505C3805C70 AcknowledgementsWe thank the referees for their suggestions which improve the presentation of the paper. The research of Ping Li is supported in part by National Natural Science Foundation of China (11301023) and the Fundamental Research Funds for the Central Universities (2013JBM090). The research of Zhengke Miao is supported in part by NSF-China grant (NSFC 11171288) and the NSF of the Jiangsu Higher Education Institutions (11KJB110014).