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
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
Received 5 October 1981; Revised 21 May 1982
Copyright © 1982 John Banks and John Mitchem. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
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.