On the acyclic point-connectivity of then-cube

[摘要] The acyclic point-connectivity of a graphG, denotedα(G), is the minimum number of points whose removal fromGresults in an acyclic graph. In a 1975 paper, Harary stated erroneously thatα(Qn)=2n−1−1whereQndenotes then-cube. We prove that forn>4,7⋅2n−4≤α(Qn)≤2n−1−2n−y−2, wherey=[log2(n−1)]. We show that the upper bound is obtained forn≤8and conjecture that it is obtained for alln.

[学科分类] 数学（综合）