Are almost all n-vertex graphs of given diameter Hamiltonian? Full article
| Journal |
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304 |
||
|---|---|---|---|
| Output data | Year: 2024, Volume: 21, Number: 2, Pages: 1549-1561 Pages count : 13 DOI: 10.33048/semi.2024.21.098 | ||
| Tags | graph, Hamiltonian graph, Hamiltonian cycle, diameter, typical graphs, almost all graphs | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0017 |
Abstract:
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.
Cite:
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
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
Dates:
| Submitted: | Dec 1, 2024 |
| Accepted: | Dec 26, 2024 |
| Published online: | Dec 31, 2024 |
Identifiers:
| Web of science: | WOS:001399958000019 |
Citing:
Пока нет цитирований