An oriented graph has weak diameter at most $d$ if every non-adjacent pair of vertices are connected by a directed $d$-path. The function $f_d(n)$ denotes the minimum number of arcs in an oriented graph on $n$ vertices having weak diameter $d$. It turns out that finding the exact value of $f_d(n)$ is a challenging problem even for $d = 2$. This function was introduced by Katona and Szeme\'redi [Studia Scientiarum Mathematicarum Hungarica, 1967], and after that several attempts were made to find its exact value by Znam [Acta Fac. Rerum Natur. Univ. Comenian. Math. Publ, 1970], Dawes and Meijer [J. Combin. Math. and Combin. Comput, 1987], F\"uredi, Horak, Pareek and Zhu [Graphs and Combinatorics, 1998], and Kostochka, Luczak, Simonyi and Sopena [Discrete Mathematics and Theoretical Computer Science, 1999] through improving its best known upper bounds. In that process, they also proved that this function is asymptotically equal to $n\log_2 n$ and hence, is an asymptotically increasing function. In this article, we prove that $f(n)$ is a strictly increasing function. Furthermore, we improve the best known upper bound of $f(n)$ and conjecture that it is tight.
翻译:一个有向图如果每个非相邻的顶点都被一个长度不超过$d$的定向路径所连接,则它的弱直径最多为$d$。函数$f_d(n)$表示$n$个顶点的有向图中弱直径为$d$的最小弧数。发现即使对于$d=2$,找到$f_d(n)$的精确值仍然是一个具有挑战性的问题。这个函数是由Katona和Szeme\'redi [Studia Scientiarum Mathematicarum Hungarica, 1967]介绍的,并且在此之后,Znam [Acta Fac. Rerum Natur. Univ. Comenian. Math. Publ, 1970]、Dawes和Meijer [J. Combin. Math. and Combin. Comput, 1987]、F\"uredi、Horak、Pareek和Zhu [Graphs and Combinatorics , 1998]和Kostochka、Luczak、Simonyi和Sopena [Discrete Mathematics and Theoretical Computer Science, 1999]通过提高它的最佳已知上界,试图找到它的精确值。在这个过程中,他们还证明了该函数的渐近值为$n\log_2 n$,因此是一个渐近递增的函数。在本文中,我们证明$f(n)$是一个严格递增的函数。此外,我们改进了$f(n)$的最佳已知上界,并猜测它是紧的。