Premium
Non‐traceability of large connected claw‐free graphs
Author(s) -
Frydrych Wacłw,
Skupień Zdzisław
Publication year - 1998
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199802)27:2<75::aid-jgt3>3.0.co;2-c
Subject(s) - combinatorics , mathematics , discrete mathematics , graph , disjoint sets , cograph , chordal graph , 1 planar graph
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 ) ≥ $\frac{5}{6}|V| - 3$ . This contrasts sharply with known results on NP‐completeness among dense graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 75–86, 1998