Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот документ:
https://elib.bsu.by/handle/123456789/7975
Заглавие документа: | Hamiltonian properties of locally connnected graphs with bounded vertex degree |
Авторы: | Gordon, Valery S. Orlovich, Yu. L. Potts, Chris N. Strusevich, Vitaly A. |
Тема: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика |
Дата публикации: | 2009 |
Библиографическое описание источника: | 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. |
Аннотация: | 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 |
Располагается в коллекциях: | Статьи факультета прикладной математики и информатики |
Полный текст документа:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
gops_hamiltonian.pdf | 363,63 kB | Adobe PDF | Открыть |
Все документы в Электронной библиотеке защищены авторским правом, все права сохранены.