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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom