Degree Sum Conditions for the Hamiltonicity and Traceability of \(L_1\)-Graphs

Rao Li1
1School of Computer and Information Sciences Georgia Southwestern State University Americus, GA 31709

Abstract

A graph \(G\) is called an \(L_1\)-graph if, for each triple of vertices \(u, v,\) and \(w\) with \(d(u,v) = 2\) and \(w \in N(u) \cap N(v)\), \(d(u) + d(v) \geq |N(u) \cup N(v) \cup N(w)| – 1\). Let \(G\) be a 2-connected \(L_1\)-graph of order \(n\). If \(\sigma_3(G) \geq n – 2\), then \(G\) is hamiltonian or \(G \in \mathcal{K}\), where \(\sigma_3(G) = \min\{d(u) + d(v) + d(w) : \{u,v,w\} \text{ is an independent set in } G\}\), \(\mathcal{K}=\{G: K_{p, p+1} \subseteq G \subseteq K_p + (p+1)K_1 for some p \geq 2\}\). A similar result on the traceability of connected \(L_1\)-graphs is also obtained.