International Journal of Mathematics and Mathematical Sciences
Volume 5 (1982), Issue 4, Pages 737-744
doi:10.1155/S0161171282000684
On the acyclic point-connectivity of the n-cube
John Banks1
and John Mitchem2
1Department of Mathematics, University of California, Santa Cruz, Santa Cruz 95064, California, USA
2Department of Mathematics and Computer Science, San Jose State University, San Jose 95192, California, USA
Abstract
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.