Hamiltonicity of \(L_1\) – Graphs with Bounded Dilworth Numbers

Abstract

Let \(u\) and \(v\) be two vertices in a graph \(G\). We say vertex \(u\) dominates vertex \(v\) if \(N(v) \subseteq N(u) \cup \{u\}\). If \(u\) dominates \(v\) or \(v\) dominates \(u\), then \(u\) and \(v\) are comparable. The Dilworth number of a graph \(G\), denoted \(\text{Dil}(G)\), is the largest number of pairwise incomparable vertices in the graph \(G\). A graph \(G\) is called \(\{H_1, H_2, \ldots, H_k\}\)-free if \(G\) contains no induced subgraph isomorphic to any \(H_i\), \(1 \leq i \leq k\). 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 \(k\) (\(k \geq 2\))-connected \(L_2\)-graph. If \(G\) is \(\{K_{1,5}, K_{1,5+e}\}\)-free and \(\text{Dil}(G) \leq 2k-1\), then \(G\) is Hamiltonian or \(G \in \mathcal{F}\), where \(K_{1,5}+e\) is a graph obtained by joining a pair of nonadjacent vertices in \(K_{s,s}\) and \(\mathcal{F} = \{G : K_{p,p-1} \subseteq G \subseteq K_{p} \vee (p+1)K_1, 2 \leq p \leq 3\}\), where \(\vee\) denotes the join operation of two graphs.