RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Tr. Inst. Mat.: Year: Volume: Issue: Page: Find

 Tr. Inst. Mat., 2012, Volume 20, Number 2, Pages 36–50 (Mi timb172)

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.

Full text: PDF file (260 kB)
References: PDF file   HTML file
UDC: 519.17

Citation: P. A. Irzhavski, Yu. L. Orlovich, “Full cycle extendability of locally connected $K_{1,4}$-restricted graphs”, Tr. Inst. Mat., 20:2 (2012), 36–50

Citation in format AMSBIB
\Bibitem{IrzOrl12} \by P.~A.~Irzhavski, Yu.~L.~Orlovich \paper Full cycle extendability of locally connected $K_{1,4}$-restricted graphs \jour Tr. Inst. Mat. \yr 2012 \vol 20 \issue 2 \pages 36--50 \mathnet{http://mi.mathnet.ru/timb172}