On the Basis Number of the Semi-Strong Product of Bipartite Graphs with Cycles

Abstract

A basis of the cycle spaceC(G) is d-fold if each edge occurs in at most d cycles of C(G). The basis number,b(G),of a graph G is defined to be the least integer d such that G has a d-fold basis for its cycle space. MacLane proved that a graph G is planar if and only if b(G) 2. Schmeichel showed that for n 5,b(K n P2) 1 + b(K n ). Ali proved that for n;m 5, b(K n K m ) 3 + b(K n )+ b(K m ). In this paper,we give an upper bound for the basis number of the semi-strong product of a bipartite graph with a cycle.