Logo BSU

Please use this identifier to cite or link to this item: http://elib.bsu.by/handle/123456789/7975
Title: Hamiltonian properties of locally connnected graphs with bounded vertex degree
Authors: Gordon, Valery S.
Orlovich, Yu. L.
Potts, Chris N.
Strusevich, Vitaly A.
Keywords: ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика
Issue Date: 2009
Citation: Orlovich, Yury L. Hamiltonian properties of locally connnected graphs with bounded vertex degree / Valery S. Gordon, Yury L. Orlovich, Chris N. Potts, Vitaly A. Strusevich //- 2009. - P.
Abstract: We consider the existence of hamiltonian cycles for locally connected graphs with a bounded vertex degree. For a graph G, let ¢(G) and ±(G) denote the maximum and minimum vertex degrees, respectively. We explicitly describe all connected, locally connected graphs with ¢(G) 6 4. We show that every connected, locally connected graph with ¢(G) = 5 and ±(G) > 3 is fully cycle extendable which extends the results of P.B. Kikust (Latvian Math. Annual 16 (1975) 33{38) and G.R.T. Hendry (J. Graph Theory 13 (1989) 257{260) on fully cycle extendability of connected, locally connected graphs with the maximum vertex degree bounded by 5. Furthermore, we prove that problem Hamilton Cycle for locally connected graphs with ¢(G) 6 7 is NP-complete. 2000 Mathematics Subject Classi¯cation: 05C38 (05C45, 68Q25).
URI: http://elib.bsu.by/handle/123456789/7975
Appears in Collections:Статьи факультета прикладной математики и информатики

Files in This Item:
File Description SizeFormat 
gops_hamiltonian.pdf363,63 kBAdobe PDFView/Open


PlumX

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.