Hamiltonicity in claw-free graphs (Q1186134): Difference between revisions

A (finite, undirected, simple) graph \(G=(V,E)\) is claw-free (CN-free; distance claw-free; \(t\)-tough; \(k\)-leaf-connected) iff \(G\) does not contain any induced subgraph isomorphic to a \(K_{1,3}\) \((G\) is claw- free and does not contain any induced subgraph isomorphic to a net, i.e. a \(K_ 3\) with a pendant leaf attached to each vertex; for each vertex \(v\in V\) and every \(i\) the subgraph induced by all vertices \(u\) with distance \(d(u,v)=i\) contains at most two independent vertices; for every \(S\subseteq V\), \(S\neq\varnothing\), the number of components of \(G-S\) is at most \(| S|/t\); for every \(S\subseteq V\) with \(| S|=k\geq 2\) there is a spanning tree of \(G\) whose leaves are exactly the vertices of \(S\), respectively). 1. The author gives a characterization of connected CN-free graphs by means of minimal cut sets and proves for CN-free graphs \(G\): If \(G\) is connected then \(G\) is traceable (i.e. there is a Hamiltonian path); if \(G\) is 2-connected then \(G\) is Hamiltonian; for \(k\geq 2\), \(G\) is \((k+1)\)- connected iff \(G\) is \(k\)-leaf-connected; if \(G\) is 3-connected then \(G\) is pancyclic (and Hamiltonian connected). Several interesting corollaries are obtained (e.g. every 1-tough CN-free graph is Hamiltonian). 2. For the class of distance claw-free graphs there is given a forbidden subgraph characterization (it follows that this class contains all CN- free graphs) and it is proved that every distance claw-free 2-connected (3-connected, i.e. 3/2-tough) graph is traceable (Hamiltonian, respectively). 3. The characterizations mentioned in 1. and 2. yield polynomial time algorithms for finding the Hamiltonian paths (cycles) and maximum weight stable sets, respectively, in the graphs considered. (Before Corollary 3.8, the numbers of the Theorems cited must be 1.3 and 3.7).