Preview

Известия Национальной академии наук Беларуси. Серия физико-математических наук

Расширенный поиск

Главные собственные значения графа и его гамильтоновость

https://doi.org/10.29235/1561-2430-2020-56-4-398-407

Полный текст:

Аннотация

Понятие (κ,τ)-регулярного множества вершин впервые появилось в 2004 г. Оказалось, что существование многих классических комбинаторных структур в графе, таких как совершенные паросочетания, гамильтоновы циклы, эффективные доминирующие множества и др., может быть охарактеризовано с помощью (κ,τ)-регулярных множеств, определение которых эквивалентно нахождению этих классических комбинаторных структур. В свою очередь определение (κ,τ)-регулярных множеств тесно связано со свойствами главного спектра графа. В статье обобщаются известные свойства (κ,κ)-регулярных множеств графа на произвольные (κ,τ)-регулярные множества графов с акцентом на связь их с классическими комбинаторными структурами. Также приводится алгоритм распознавания гамильтоновости графа, который становится полиномиальным в некоторых классах графов, например в классе графов с фиксированным цикломатическим числом.

Об авторе

В. И. Бенедиктович
Институт математики Национальной академии наук Беларуси
Беларусь

Бенедиктович Владимир Иванович – кандидат физико-математических наук, ведущий научный сотрудник

ул. Сурганова, 11, 220072, г. Минск



Список литературы

1. Гантмахер, Ф. Р. Теория матриц / Ф. Р. Гантмахер. – Физматлит, 2010. – 560 с.

2. Cvetković, D. A table of connected graphs on six vertices / D. Cvetković, M. Petrić // Discrete Math. – 1984. – Vol. 50. – P. 37–49. https://doi.org/10.1016/0012-365x(84)90033-5

3. Sciriha, I. Necessary and sufficient conditions for a Hamiltonian graphs / I. Sciriha, D. M. Cardoso // J. Combin. Math. Combin. Comput. – 2012. – Vol. 80. – P. 127–150.

4. Cardoso, D. M. An overview of (κ,τ)-regular sets and their applications / D. M. Cardoso //Discrete Appl. Math. – 2019. – Vol. 269. – P. 2–10. https://doi.org/10.1016/j.dam.2018.12.020

5. Cardoso, D. M. Main eigenvalues and (κ,τ)-regular sets / D. M. Cardoso, I. Sciriha, C. Zerafa // Linear Algebra Appl. – 2010. – Vol. 432, № 9. – P. 2399–2408. https://doi.org/10.1016/j.laa.2009.07.039

6. Cvetković, D. Spectral Generalizations of Line Graphs / D. Cvetković, P. Rowlinson, S. Simić. – Cambridge University Press, 2004. https://doi.org/10.1017/cbo9780511751752


Просмотров: 72


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1561-2430 (Print)
ISSN 2524-2415 (Online)