The basis number of the powers of the complete graph Original Research Article

A basis of the cycle space C(G) of a graph G is h-fold if each edge of G occurs in at most h cycles of the basis. The basis number b(G) of G is the least integer h such that C(G) has an h-fold basis. MacLane (1937) showed that a graph G is planar if and only if b(G)⩽2. Schmeichel (1981) proved that b(Kn)⩽3, and Banks and Schmeichel (1982) proved that b(K2d)⩽4 where K2d is the d-dimensional hypercube. We show that b(Knd)⩽9 for any n and d, where Knd is the cartesian dth power of the complete graph Kn.