The Outercoarseness of the n-cube

  • Alex Fink Queen Mary University of London
  • Richard K Guy
Keywords: outerplanarity, packing, outercoarseness, $n$-cube


Guy and Nowakowski showed that the outercoarsenessof the n-cube was, for sufficiently large n, at least 0.96 of its maximum possible value, $n\cdot2^{n\!-\!4}$. Here we give some exact results, including that the maximum is attained for all $n\geq24$.


R. K. Guy, Combinatorics: Proc. British Comb. Conf., Aberystwyth, 1973, ch. Outerthickness and outercoarseness of graphs, pp. 57-60, Cambridge University Press, 1974, MR 0347652.

R. K. Guy and R. J. Nowakowski, Topics in combinatorics and graph theory: essays in honour of Gerhard Ringel, ch. The outerthickness & outercoarseness of graphs, I. The complete graph & the n-cube, pp. 297-310, Physica-Verlag, Heidelberg, 1990, MR 1100049.

R. Halin, Uber einen graphentheoretischen Basisbegriff und seine Anwendung auf Farbensprobleme, Ph.D. thesis, Universit at zu Koln, 1962.

F. Harary, J. P. Hayes, and H.-J. Wu, A survey of the theory of hypercube graphs, Comput. Math. Applic. 15 (1988), no. 4, 277-289.

J. Hartman, Bounds on the coarseness of the n-cube, Canad. Math. Bull. 22 (1979), 171-175, MR 1100049.

P. C. Kainen, Thickness and coarseness of graphs, Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg 39 (1973), no. 1, 88-95, MR 0335322.