Complete Minors in Cubic Graphs with few short Cycles and Random Cubic Graphs
Complete Minors in Cubic Graphs with few short Cycles and Random Cubic Graphs
复制标题
具有少量短循环的三次图和随机三次图的完整辅项
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
K. Markström
中科院分区：
文献类型：
--
作者：
K. Markström
我们首先证明了对于任意固定的kappa，具有几个短循环的三次图包含一个K-kappa-minor。这是托马森关于周长结果的直接推广。然后我们用这个定理证明了对于任意固定k，一个随机三次图近渐地几乎肯定包含一个kk次图。
We first prove that for any fixed kappa a cubic graph with few short cycles contains a K-kappa-minor. This is a direct generalisation of a result on girth by Thomassen. We then use this theorem to show that for any fixed k a random cubic graph contains a Kk-minor asymptotically almost surely.