Non-traceability of large connected claw-free graphs

✍ Scribed by Frydrych, Wac?w; Skupie?, Zdzis?aw

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 209 KB
• Volume: 27
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199802)27:2<75::aid-jgt3>3.0.co;2-c

✦ Synopsis

Let G be a connected claw-free graph on n vertices. Let σ 3 (G) be the minimum degree sum among triples of independent vertices in G. It is proved that if σ 3 (G) ≥ n-3 then G is traceable or else G is one of graphs G n each of which comprises three disjoint nontrivial complete graphs joined together by three additional edges which induce a triangle K 3 . Moreover, it is shown that for any integer k ≥ 4 there exists a positive integer ν(k) such that if σ 3 (G) ≥ n -k, n > ν(k) and G is non-traceable, then G is a factor of a graph G n . Consequently, the problem HAMILTONIAN PATH restricted to claw-free graphs G = (V, E) (which is known to be NP-complete) has linear time complexity O(|E|) provided that σ 3 (G) ≥ 5 6 |V | -3. This contrasts sharply with known results on NP-completeness among dense graphs.