Independence Number, Neighborhood Intersection and Hamiltonian Properties
Author(s) -
Fan Yunzheng
Publication year - 2009
Publication title -
boletim da sociedade paranaense de matemática
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.347
H-Index - 15
eISSN - 2175-1188
pISSN - 0037-8712
DOI - 10.5269/bspm.v22i2.7480
Subject(s) - backslash , independence number , combinatorics , mathematics , hamiltonian (control theory) , graph , intersection (aeronautics) , discrete mathematics , physics , mathematical optimization , engineering , aerospace engineering
Let G be a 2-connected simple graph of order n with the independence number\alpha. We show here that \forall u; v \in V (G)\backslash\{u,v\} and any z \in \{u,v\}; w \in V (G)\backslash \{u,v\}; with d(w; z) = 2, if |N(u) \ cap N(w)| \geq \alpha - 1 or |N(v) \cap N(w)| \geq \alpha - 1, then G is Hamiltonian, unless G belongs to a kind of special graphs.
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