×

Pairs of forbidden subgraphs and 2-connected supereulerian graphs. (English) Zbl 1384.05104

Summary: Let \(G\) be a 2-connected claw-free graph. We show that:
(i) if \(G\) is \(N_{1, 1, 4}\)-free or \(N_{1, 2, 2}\)-free or \(Z_5\)-free or \(P_8\)-free, respectively, then \(G\) has a spanning Eulerian subgraph (i.e. a spanning connected even subgraph) or its closure is the line graph of a graph in a family of well-defined graphs,
(ii) if the minimum degree \(\delta(G) \geq 3\) and \(G\) is \(N_{2, 2, 5}\)-free or \(Z_9\)-free, respectively, then \(G\) has a spanning Eulerian subgraph or its closure is the line graph of a graph in a family of well-defined graphs.
Here \(Z_i\) (\(N_{i, j, k}\)) denotes the graph obtained by attaching a path of length \(i \geq 1\) (three vertex-disjoint paths of lengths \(i, j, k \geq 1\), respectively) to a triangle.
Combining our results with a result in [L. Xiong, ibid. 332, 15–22 (2014; Zbl 1298.05193)], we prove that all 2-connected hourglass-free claw-free graphs \(G\) with one of the same forbidden subgraphs above (or additionally \(\delta(G) \geq 3\)) are Hamiltonian with the same excluded families of graphs. In particular, we prove that every 3-edge-connected claw-free hourglass-free graph that is \(N_{2, 2, 5}\)-free or \(Z_9\)-free is Hamiltonian.

MSC:

05C45 Eulerian and Hamiltonian graphs
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Citations:

Zbl 1298.05193
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer · Zbl 1226.05083
[2] Broersma, H. J.; Ryjáček, Z.; Vrána, P., How many conjectures can you stand? A survey, Graphs Combin., 28, 57-75 (2012) · Zbl 1234.05146
[3] Brousek, J., Forbidden triples for hamiltonicity, Discrete Math., 251, 71-76 (2002) · Zbl 1002.05044
[4] Brousek, J.; Ryjáček, Z.; Favaron, O.; subgraphs, Forbidden., Forbidden subgraphs hamiltonicity and closure in claw-free graphs, Discrete Math., 196, 29-50 (1999) · Zbl 0927.05053
[5] Brousek, J.; Ryjáček, Z.; Schiermeyer, I., Forbidden subgraphs, stability and hamiltonicity, Discrete Math., 197/198, 143-155 (1999) · Zbl 0929.05054
[6] Faudree, R. J.; Gould, R., Characterizing forbidden pairs for hamiltonian properties, Discrete Math., 173, 45-60 (1997) · Zbl 0879.05050
[7] Faudree, R. J.; Gould, R.; Jacobson, M. S., Forbidden triples implying hamiltonicity: for all graphs, Discussiones Math. Graph Theory, 24, 47-54 (2004) · Zbl 1060.05063
[8] Harary, F.; Nash-Williams, C. St. J.A., On eulerian and hamiltonian graphs and line graphs, Canad. Math. Bull., 8, 701-710 (1965) · Zbl 0136.44704
[9] Lv, S.; Xiong, L., Forbidden pairs for spanning (closed) trails, Discrete Math., 340, 1012-1018 (2017) · Zbl 1357.05105
[10] Lv, S.; Xiong, L., Erratum to “Forbidden pairs for spanning (closed) trails” [Discrete Math. 340 (2017) 1012-1018], Discrete Math., 341, 1192-1193 (2018) · Zbl 1408.05091
[11] Ryjáček, Z., On a closure concept in claw-free graphs, J. Comb. Theory Ser. B, 70, 2, 217-224 (1997) · Zbl 0872.05032
[12] Ryjáček, Z.; Saito, A.; Schelp, R. H., Closure, 2-factor and cycle coverings in claw-free graphs, J. Graph Theory, 32, 109-117 (1999) · Zbl 0932.05045
[13] Xiong, L., Closure operation for even factors on claw-free graphs, Discrete Math., 311, 1714-1723 (2011) · Zbl 1235.05116
[14] Xiong, L., Induced hourglass and the equivalence between hamiltonicity and supereulerianity in claw-free graphs, Discrete Math., 332, 15-22 (2014) · Zbl 1298.05193
[15] Xiong, L.; Li, M. C., Supereulerian index is stable under contractions and closures, Ars Combin., 97, 129-142 (2010) · Zbl 1249.05241
[16] Xiong, L.; Liu, Z.; Yi, G., Characterization of the \(n\) th super-eulerian iterated line graph, J. Jiangxi Normal Univ., 24, 107-121 (2000), (in Chinese) · Zbl 1009.05122
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.