Title | ||
---|---|---|
Supereulerian graphs with small matching number and 2-connected hamiltonian claw-free graphs |
Abstract | ||
---|---|---|
Motivated 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 wellknown theorem by Chvatal and Erdos [A note on Hamilton circuits, Discrete Math. 2 (1972), pp. 111-135] states that if G satisfies alpha(G) <= kappa G), then G is hamiltonian. Flandrin and Li in 1989 showed that every 3-connected claw-free graph G with alpha(G) <= 2 kappa(G) is hamiltonian. Our characterization is also applied to show that every 2-connected claw-free graph G with alpha(G) <= 3 is hamiltonian, with only one well-characterized exceptional class. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1080/00207160.2013.858808 | International Journal of Computer Mathematics |
Keywords | Field | DocType |
collapsible graphs,contraction characterizations,reductions,supereulerian graphs | Discrete mathematics,Indifference graph,Combinatorics,Forbidden graph characterization,Chordal graph,Cograph,Pathwidth,1-planar graph,Mathematics,Pancyclic graph,Split graph | Journal |
Volume | Issue | ISSN |
91 | 8 | 0020-7160 |
Citations | PageRank | References |
1 | 0.38 | 11 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jinquan Xu | 1 | 18 | 6.20 |
Ping Li | 2 | 21 | 7.14 |
Zhengke Miao | 3 | 1 | 0.38 |
Keke Wang | 4 | 2 | 1.43 |
Hong-Jian Lai | 5 | 631 | 97.39 |