Full cycle extendability of locally connected $K_{1,4}$-restricted graphs

P. A. Irzhavski, Yu. L. Orlovich

Belarusian State University, Minsk

Abstract: In this paper we show that a connected locally connected $K_{1,4}$-restricted graph on at least three vertices is either fully cycle extendable or isomorphic to one of the five exceptional (non-Hamiltonian) graphs. This result generalizes several known results on the existence of Hamiltonian cycles in locally connected graphs. We also propose a polynomial time algorithm for finding a Hamiltonian cycle in graphs under consideration.

UDC: 519.17

Received: 14.11.2012