For integers $k,g,d$, a $(k;g,d)$-cage (or simply girth-diameter cage) is a smallest $k$-regular graph of girth $g$ and diameter $d$ (if it exists). The order of a $(k;g,d)$-cage is denoted by $n(k;g,d)$. We determine asymptotic lower and upper bounds for the ratio between the order and the diameter of girth-diameter cages as the diameter goes to infinity. We also prove that this ratio can be computed in constant time for fixed $k$ and $g$. We theoretically determine the exact values $n(3;g,d)$, and count the number of corresponding girth-diameter cages, for $g \in \{4,5\}$. Moreover, we design and implement an exhaustive graph generation algorithm and use it to determine the exact order of several open cases and obtain -- often exhaustive -- sets of the corresponding girth-diameter cages. The largest case we generated and settled with our algorithm is a $(3;7,35)$-cage of order 136.


翻译:对于整数 $k,g,d$,一个 $(k;g,d)$-笼图(或简称为围长-直径笼图)是具有围长 $g$ 和直径 $d$ 的最小 $k$-正则图(若其存在)。$(k;g,d)$-笼图的阶记为 $n(k;g,d)$。我们确定了当直径趋于无穷大时,围长-直径笼图的阶与直径之比的渐近下界和上界。我们还证明了对于固定的 $k$ 和 $g$,该比值可以在常数时间内计算。我们从理论上确定了 $n(3;g,d)$ 的精确值,并统计了 $g \\in \\{4,5\\}$ 时对应的围长-直径笼图的数量。此外,我们设计并实现了一种穷举图生成算法,并用其确定了若干开放案例的精确阶数,并获得了——通常是穷举的——对应围长-直径笼图集合。我们通过算法生成并解决的最大案例是一个阶为 136 的 $(3;7,35)$-笼图。

0
下载
关闭预览

相关内容

FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
34+阅读 · 2019年10月18日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
43+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
相关基金
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员