Spanning paths and cycles in triangle-free graphs

Abstract

Let G be a simple, connected, triangle-free graph with minimum degree δ and leaf number L(G). We prove that if L(G) ≤2δ − 1, then G is either Hamiltonian or G ∈ ℱ₂, where ℱ₂ is the class of non-Hamiltonian graphs with leaf number 2δ − 1. Further, if L(G) ≤ 2δ, we show that G is traceable or G ∈ ℱ₃. The results, apart from strengthening theorems in [17, 16] 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.

Mathematics Subject Classification (2010):

• 05C05
• 05C38
• 05C45

Key words:

• Leaf number
• minimum degree
• Hamiltonicity
• traceability