×

Spanning paths and cycles in triangle-free graphs. (English) Zbl 1459.05043

Summary: Let \(G\) be a simple, connected, triangle-free graph with minimum degree \(\delta\) and leaf number \(L(G)\). We prove that if \(L(G) \leq 2\delta - 1\), then \(G\) is either Hamiltonian or \(G \in \mathcal{F}_2\), where \(\mathcal{F}_2\) is the class of non-Hamiltonian graphs with leaf number \(2 \delta - 1\). Further, if \(L(G) \leq 2\delta \), we show that \(G\) is traceable or \(G \in \mathcal{F}_3\). The results, apart from strengthening theorems in [P. Mafuta et al., Acta Math. Hung. 152, No. 1, 217–226 (2017; Zbl 1389.05094); P. Mafuta et al., Discrete Appl. Math. 255, 278–282 (2019; Zbl 1405.05088)] for this class of graphs, provide a sufficient condition for a triangle-free graph to be Hamiltonian or traceable based on leaf number and minimum degree.

MSC:

05C05 Trees
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aung, M., Longest cycles in triangle-free graphs, Journal of Combinatorial Series B, 47, 2, 171-186 (1989) · Zbl 0634.05046
[2] Bauer, D.; Kahl, N.; McGuire, L.; Schmeichel, E., Long cycles in 2-connected triangle-free graphs, Ars Combinatoria, 86, 295-304 (2008) · Zbl 1224.05257
[3] Brandt, S., Cycles and paths in triangle-free graphs, The mathematics of Paul Erdős, 14, 32-42 (1997), Springer: Springer, Berlin · Zbl 0867.05036
[4] Broersma, H. J.; van den Heuvel, J.; Veldman, H. J., A generalisation of Ore’s Theorem involving neighbourhood unions, Discrete Mathematics, 122, 37-49 (1993) · Zbl 0789.05058
[5] DeLavina, E., Written on the wall II (Conjectures of Graffiti.pc), http://cms.dt.uh.edu/faculty/delavinae/research/wow II/, 104, 167-183 (2005)
[6] Dirac, G. A., Some theorems on abstract graphs, Proceedings of the London Mathematical Society, 2, 69-81 (1952) · Zbl 0047.17001
[7] Faudree, R.; Flandrin, E.; Ryjáček, Z., Claw-free graphs-a survey, Discrete Mathematics, 164, 87-147 (1997) · Zbl 0879.05043
[8] Fernandes, L. M.; Gouvea, L., Minimal spanning trees with a constraint on the number of leaves, European Journal of Operational Research, 104, 250-261 (1998) · Zbl 0957.90010
[9] Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company, San Francisco, CA · Zbl 0411.68039
[10] Gould, R. J., Advances on Hamiltonian problem-A survey, Graphs and Combinatorics, 19, 1, 7-52 (2003) · Zbl 1024.05057
[11] Hilbig, F., Kantenstruckturen in nichthamiltonschen Graphen, Ph.D. Thesis, Technische Universität, Berlin, Germany, 1986. · Zbl 0614.05033
[12] Jackson, B., Neighbourhood unions and Hamilton cycles, Journal of Graph Theory, 15, 443-451 (1991) · Zbl 0739.05058
[13] Li, H., Hamiltonian cycles in 2-connected claw-free graphs, Journal of Graph Theory, 20, 447-457 (1995) · Zbl 0841.05062
[14] Mafuta, P., Leaf number and Hamiltonian C4-free graphs, Afrika Matematika (2017) · Zbl 1379.05071
[15] Mafuta, P.; Mukwembi, S., On minimum degree, leaf number, traceability and Hamiltonicity in graphs, Discrete Applied Mathematics, 221, 89-94 (2017) · Zbl 1357.05073
[16] Mafuta, P.; Mukwembi, S.; Munyira, S., Spanning paths in graphs, Discrete Applied Mathematics (2018) · Zbl 1405.05088 · doi:10.1016/j.dam.2018.08.001
[17] Mafuta, P.; Mukwembi, S.; Munyira, S.; Vetrík, T., Hamiltonicity, leaf number and minimum degree, Acta Mathematica Hungarica, 152, 1, 217-226 (2017) · Zbl 1389.05094
[18] Mukwembi, S., Minimum degree, leaf number and traceability, Czechoslovak Mathematical Journal, 63, 138, 539-545 (2013) · Zbl 1289.05261
[19] Mukwembi, S., On Spanning cycles, paths and trees, Discrete Applied Mathematics, 161, 2217-2222 (2013) · Zbl 1287.05080
[20] Mukwembi, S., Minimum degree, leaf number, and Hamiltonicity, American Mathematical Monthly, 120, 2, 115 (2013) · Zbl 1264.05076
[21] Nash-Williams, J. A., Edge-disjoint hamiltonian circuits in graphs with vertices of large valency, 157-183 (1971), Academic Press: Academic Press, London · Zbl 0223.05123
[22] Nikoghosyan, Zh. G., Graph invariants and large cycles: A survey, International Journal of Mathematics and Mathematical Sciences, 2011 (2011) · Zbl 1213.05221
[23] Ren, S., A sufficient condition for graphs with large neighbourhoods unions to be traceable, Discrete Mathematics, 161, 229-234 (1996) · Zbl 0869.05041
[24] Ore, O., A note on Hamiltonian circuits, American Mathematical Monthly, 67, 55 (1960) · Zbl 0089.39505
[25] Ozeki, K.; Yamashita, T., Spanning trees-A survey, Graphs and Combinatorics, 27, 1-26 (2011) · Zbl 1232.05055
[26] Ozeki, K.; Yamashita, T., Length of longest cycles in a graph whose relative length is at least two, Graphs and Combinatorics, 28, 859-868 (2012) · Zbl 1256.05126
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.