Premium
Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
Author(s) -
Oberly David J.,
Sumner David P.
Publication year - 1979
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/jgt.3190030405
Subject(s) - mathematics , combinatorics , distance hereditary graph , quartic graph , line graph , factor critical graph , connected component , hamiltonian (control theory) , discrete mathematics , strongly connected component , graph , graph power , mathematical optimization
A graph is locally connected if every neighborthood induces a connected subgraph. We show here that every connected, locally connected graph on p ≥ 3 vertices and having no induced K 1,3 is Hamiltonian. Several sufficient conditions for a line graph to be Hamiltonian are obtained as corollaries.