JEDNOSTKA NAUKOWA KATEGORII A+

# Wydawnictwa / Czasopisma IMPAN / Colloquium Mathematicum / Wszystkie zeszyty

## A note on the Song–Zhang theorem for Hamiltonian graphs

### Tom 120 / 2010

Colloquium Mathematicum 120 (2010), 63-75 MSC: 05C38, 05C45. DOI: 10.4064/cm120-1-5

#### Streszczenie

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 \neq v \in S$ such that $d(u) + d(v) \geq n$ or $|N(u) \cap N(v)| \geq \alpha (G)$;

(ii) for any distinct $u$ and $v$ in $S$, $|N(u) \cup N(v)| \geq n - \max \{d(x): x \in 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.

#### Autorzy

• Kewen ZhaoDepartment of Mathematics
Qiongzhou University
Sanya, Hainan 572022
P.R. China
e-mail
• Ronald J. GouldDeptartment of Mathematics and Computer Science
Emory University
Atlanta, GA 30322, U.S.A.
e-mail

## Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Odśwież obrazek