Premium
An improvement of fraisse's sufficient condition for hamiltonian graphs
Author(s) -
Ainouche A.
Publication year - 1992
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.3190160602
Subject(s) - combinatorics , mathematics , vertex (graph theory) , hamiltonian (control theory) , graph , hamiltonian path , bound graph , discrete mathematics , graph power , line graph , mathematical optimization
Let G be a k ‐connected graph of order n . For an independent set c, let d(S) be the number of vertices adjacent to at least one vertex of S and > let i(S) be the number of vertices adjacent to at least |S| vertices of S . We prove that if there exists some s, 1 ≤ s ≤ k, such that Σ x i EX d(X\{X i }) > s(n−1) – k[s/2] – i (X)[(s−1)/2] holds for every independetn set X ={x 0 , x 1 ⃛x s } of s + 1 vertices, then G is hamiltonian. Several known results, including Fraisse's sufficient condition for hamiltonian graphs, are dervied as corollaries.