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)$的最佳已知上界,并猜测它是紧的。

0
下载
关闭预览

相关内容

有向图模型又称为贝叶斯网络,属于概率图模型中的一类。
【干货书】工程和科学中的概率和统计,
专知会员服务
57+阅读 · 2022年12月24日
专知会员服务
76+阅读 · 2021年3月16日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Reinforcement Learning: An Introduction 2018第二版 500页
CreateAMind
11+阅读 · 2018年4月27日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年5月23日
Arxiv
0+阅读 · 2023年5月23日
Arxiv
0+阅读 · 2023年5月19日
Arxiv
0+阅读 · 2023年5月18日
VIP会员
相关VIP内容
【干货书】工程和科学中的概率和统计,
专知会员服务
57+阅读 · 2022年12月24日
专知会员服务
76+阅读 · 2021年3月16日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Reinforcement Learning: An Introduction 2018第二版 500页
CreateAMind
11+阅读 · 2018年4月27日
相关基金
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员