Hamilton – Connectivity of Claw – Free 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 \(\operatorname{Dil}(G)\), is the largest number of pairwise incomparable vertices in the graph \(G\). A graph \(G\) is called claw-free if \(G\) has no induced subgraph isomorphic to \(K_{1,3}\). It is shown that if \(G\) is a \(k\) (\(k \geq 3\)) – connected claw-free graph with \(\operatorname{Dil}(G) \leq 2k-5\), then \(G\) is Hamilton-connected and a Hamilton path between every two vertices in \(G\) can be found in polynomial time.