Hamiltonian cycles in spanning subgraphs of line graphs. (English) Zbl 1339.05217
Summary: Let \(G\) be a graph and \(e = u v\) an edge in \(G\) (also a vertex in the line graph \(L(G)\) of \(G\)). Then \(e\) is in two cliques \(E_G(u)\) and \(E_G(v)\) with \(E_G(u) \cap E_G(v) = \{e \}\) of \(L(G)\), that correspond to all edges incident with \(u\) and \(v\) in \(G\) respectively. Let \(S L(G)\) be any spanning subgraph of \(L(G)\) such that every vertex \(e = u v\) is adjacent to at least \(\min \{d_G(u) - 1, \lceil \frac{3}{4} d_G(u) + \frac{1}{2} \rceil \}\) vertices of \(E_G(u)\) and to at least \(\min \{d_G(v) - 1, \lceil \frac{3}{4} d_G(v) + \frac{1}{2} \rceil \}\) vertices of \(E_G(v)\). Then if \(L(G)\) is Hamiltonian, we show that \(S L(G)\) is Hamiltonian. As a corollary we obtain a lower bound on the number of edge-disjoint Hamiltonian cycles in \(L(G)\).
MSC:
| 05C45 | Eulerian and Hamiltonian graphs |
| 05C76 | Graph operations (line graphs, products, etc.) |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
References:
| [1] | Alspach, B.; Bermond, J. C.; Sotteau, D., Decomposition into cycles I: Hamilton decompositions, (Hahn, G.; etal., Cycle and Rays (1990), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 9-18 · Zbl 0713.05047 |
| [2] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Macmillan, London and Elsevier: Macmillan, London and Elsevier New York · Zbl 1226.05083 |
| [3] | Harary, F.; Nash-Williams, C. St. J.A., On the eulerian and hamiltonian graphs and line graphs, Can. Math. Bull., 8, 701-710 (1965) · Zbl 0136.44704 |
| [4] | Kaiser, T.; Vrána, P., Hamilton cycles in 5-connected line graphs, European J. Combin., 33, 5, 924-947 (2012) · Zbl 1239.05113 |
| [5] | Lai, H.; Shao, Y.; Wu, H.; Zhou, J., Every 3-connected, essentially 11-connected line graph is Hamiltonian, J. Combin. Theory Ser. B, 96, 571-576 (2006) · Zbl 1091.05040 |
| [6] | Li, H.; Yang, W., Every 3-connected essentially 10-connected line graph is hamiltonian connected, Discrete Math., 312, 3670-3674 (2012) · Zbl 1254.05167 |
| [7] | Matthews, M. M.; Sumner, D. P., Hamiltonian results in \(K_{1, 3}\)-free graphs, J. Graph Theory, 8, 139-146 (1984) · Zbl 0536.05047 |
| [8] | Ryjáček, Z., On a closure concept in claw-free graphs, J. Combin. Theory Ser. B, 70, 217-224 (1997) · Zbl 0872.05032 |
| [9] | Thomassen, C., Reflections on graph theory, J. Graph Theory, 10, 309-324 (1986) · Zbl 0614.05050 |
| [10] | Yang, W.; Lai, H.; Li, H.; Guo, X., Collapsible graphs and Hamiltonian connectivity of line graphs, Discrete Appl. Math., 160, 1837-1844 (2012) · Zbl 1245.05078 |
| [11] | Zhan, S., On Hamiltonian line graphs and connectivity, Discrete Math., 89, 89-95 (1991) · Zbl 0727.05037 |
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.
