|
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.
Received: 14.11.2012
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
Linking options:
https://www.mathnet.ru/eng/timb172 https://www.mathnet.ru/eng/timb/v20/i2/p36
|
Statistics & downloads: |
Abstract page: | 364 | Full-text PDF : | 325 | References: | 63 |
|