Are almost all n-vertex graphs of given diameter Hamiltonian? | Sciact - Система учета научной деятельности ИМ СО РАН

Are almost all n-vertex graphs of given diameter Hamiltonian? Научная публикация

Журнал

Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304

Вых. Данные

Год: 2024, Том: 21, Номер: 2, Страницы: 1549-1561 Страниц : 13 DOI: 10.33048/semi.2024.21.098

Ключевые слова

graph, Hamiltonian graph, Hamiltonian cycle, diameter, typical graphs, almost all graphs

Авторы

Fedoryaeva T.I. ¹

Организации

1	Sobolev Institute of Mathemati

Информация о финансировании (1)

Институт математики им. С.Л. Соболева СО РАН

FWNF-2022-0017

Typical Hamiltonian properties of the class of n-vertex graphs of a fixed diameter k are studied. A new class of typical n-vertex graphs of a given diameter is constructed. The question of S.V. Avgustinovich on the Hamiltonian property of almost all such n-vertex graphs has been solved. It is proved that almost all n-vertex graphs of fixed diameter k=1,2,3 are Hamiltonian, while almost all n-vertex graph of fixed diameter k≥ 4 are nonHamiltonian graphs. All found typical Hamiltonian properties of n-vertex graphs of a fixed diameter k≥1 are also typical for connected graphs of diameter at least k, as well as for graphs (not necessarily connected) containing the shortest path of length at least k.

Fedoryaeva T.I.
Are almost all n-vertex graphs of given diameter Hamiltonian?
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2024. V.21. N2. P.1549-1561. DOI: 10.33048/semi.2024.21.098 WOS

Поступила в редакцию:	1 дек. 2024 г.
Принята к публикации:	26 дек. 2024 г.
Опубликована online:	31 дек. 2024 г.

Web of science:

WOS:001399958000019

Пока нет цитирований