Primality of trees
Primality of trees
复制标题
树的本原性
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
A. Taraz
中科院分区：
文献类型：
--
作者：
P. Haxell;O. Pikhurko;A. Taraz
如果一个 n 阶图可以双射地用整数 1,... 来标记它的顶点，那么它就是素数。 。 。 , n 以便任意两个相邻顶点获得互质标签。我们证明所有分隔符大小最多为 n1−Od(1/ ln lnn) 的二分 d 简并图都是素数。紧接着，所有大树都是素数，这证实了 Entringer 和 Tout 在 1980 年左右的一个古老猜想。此外，我们的方法允许我们确定所有大 n 的非素数连通 n 阶图的最小尺寸，证明了 Rao [R. C. Bose 百年离散数学研讨会。和应用，加尔各答，2002]在这个范围内。
A graph of order n is prime if one can bijectively label its vertices with integers 1, . . . , n so that any two adjacent vertices get coprime labels. We prove that all bipartite d-degenerate graphs with separators of size at most n1−Od(1/ ln lnn) are prime. It immediately follows that all large trees are prime, confirming an old conjecture of Entringer and Tout from around 1980. Also, our method allows us to determine the smallest size of a non-prime connected order-n graph for all large n, proving a conjecture of Rao [R. C. Bose Centenary Symposium on Discrete Math. and Applications, Kolkata, 2002] in this range.