International Journal of Mathematics and Mathematical Sciences
Volume 5 (1982), Issue 4, Pages 737-744

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

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.


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)=2n11 where Qn denotes the n-cube. We prove that for n>4, 72n4α(Qn)2n12ny2, where y=[log2(n1)]. We show that the upper bound is obtained for n8 and conjecture that it is obtained for all n.