pipette
ENEnglish

An asymptotically tight bound on oriented diameter

Jiangdong Ai, Yaojun Chen, Yaokun Feng, Hui Lei, Jifu Lin, Zijian Ren, Xiaolin Wang, Ruilin Zheng

Preprint

En palabras de los autores

Let be the smallest integer such that every finite connected bridgeless simple graph of diameter admits a strong orientation of diameter at most . Chv\'atal and Thomassen (1978) proved . In this paper, we prove that for every , which shows that and determines both the quadratic and linear terms up to a bounded additive error. The key method of our proof is to construct a central subgraph that admits a strong orientation of diameter and is within distance of every vertex outside it. We obtain the sharp linear coefficient by jointly estimating outside paths and their connecting paths in at the actual attachment vertices, rebuilding when necessary.

Resultado principalLimitación que admiten los autores

Apareció: jueves, 8 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 28 pages