An asymptotically tight bound on oriented diameter
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.
Apareció: jueves, 8 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 28 pages