On Directed and Undirected Diameters of Vertex-Transitive Graphs Научная публикация
| Журнал |
Combinatorica
ISSN: 0209-9683 , E-ISSN: 1439-6912 |
||
|---|---|---|---|
| Вых. Данные | Год: 2024, Том: 44, Страницы: 1353–1366 Страниц : 14 DOI: 10.1007/s00493-024-00120-4 | ||
| Ключевые слова | 20B25, Primary 05C12, Secondary 05C20 | ||
| Авторы |
|
||
| Организации |
|
Информация о финансировании (1)
| 1 | Институт математики им. С.Л. Соболева СО РАН | FWNF-2022-0002 |
Реферат:
Adirected diameter of a directed graph is the maximum possible distance between a pair of vertices, where paths mustrespect edgeorientations, while undirected diameter is the diameter of the undirected graph obtained by symmetrizing the edges. In 2006 Babai proved that for a connected directed Cayley graph on n vertices the directed diameter is bounded above by a polynomial in undirected diameter and logn. Moreover, Babai conjectured that a similar bound holds for vertex-transitive graphs. We prove this conjecture of Babai, in fact, it follows from a more general bound for connected relations of homogeneous coherent configurations. The main novelty of the proof is a generalization of Ruzsa’s triangle inequality from additive combinatorics to the setting of graphs
Библиографическая ссылка:
Skresanov S.V.
On Directed and Undirected Diameters of Vertex-Transitive Graphs
Combinatorica. 2024. V.44. P.1353–1366. DOI: 10.1007/s00493-024-00120-4 WOS Scopus РИНЦ OpenAlex
On Directed and Undirected Diameters of Vertex-Transitive Graphs
Combinatorica. 2024. V.44. P.1353–1366. DOI: 10.1007/s00493-024-00120-4 WOS Scopus РИНЦ OpenAlex
Даты:
| Поступила в редакцию: | 23 янв. 2024 г. |
| Принята к публикации: | 27 июн. 2024 г. |
| Опубликована online: | 9 июл. 2024 г. |
| Опубликована в печати: | 20 нояб. 2024 г. |
Идентификаторы БД:
| Web of science: | WOS:001268956800001 |
| Scopus: | 2-s2.0-85197801234 |
| РИНЦ: | 68767018 |
| OpenAlex: | W4400465025 |