Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

A note on the Song-Zhang theorem for Hamiltonian graphs

100%

Zhao K., Gould R.

Colloquium Mathematicum

2010

tom 120

nr 1

63-75

An independent set S of a graph G is said to be essential if S has a pair of vertices that are distance two apart in G. In 1994, Song and Zhang proved that if for each independent set S of cardinality k+1, one of the following condition holds: (i) there exist u ≠ v ∈ S such that d(u) + d(v) ≥ n or |N(u) ∩ N(v)| ≥ α (G); (ii) for any distinct u and v in S, |N(u) ∪ N(v)| ≥ n - max{d(x): x ∈ S}, then G is Hamiltonian. We prove that if for each essential independent set S of cardinality k+1, one of conditions (i) or (ii) holds, then G is Hamiltonian. A number of known results on Hamiltonian graphs are corollaries of this result.

Ograniczanie wyników

1 Colloquium Mathematicum

1 Gould R.

1 Zhao K.

1 2010

Wyniki wyszukiwania

A note on the Song-Zhang theorem for Hamiltonian graphs