文章基本信息

标题：On the acyclic point-connectivity of the <mml:math alttext="$n$" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math>-cube
本地全文：下载
作者：John Banks ; John Mitchem
期刊名称：International Journal of Mathematics and Mathematical Sciences
印刷版ISSN：0161-1712
电子版ISSN：1687-0425
出版年度：1982
卷号：5
DOI：10.1155/S0161171282000684
出版社：Hindawi Publishing Corporation
摘要：The acyclic point-connectivity of a graph G, denoted α(G), is the minimum number of points whose removal from G results in an acyclic graph. In a 1975 paper, Harary stated erroneously that α(Qn)=2n−1−1 where Qn denotes the n-cube. We prove that for n>4, 7⋅2n−4≤α(Qn)≤2n−1−2n−y−2, where y=[log2(n−1)]. We show that the upper bound is obtained for n≤8 and conjecture that it is obtained for all n.