The basis number of the strong product of paths and cycles with bipartite graphs

Abstract

The basis number of a graph G is defined to be the least integer d such that there is a basis B of the cycle space of G such that each edge of G is contained in at most d members of B. MacLane [13] proved that a graph G is planar if and only if the basis number of G is less than or equal to 2. Ali [3] proved that the basis number of the strong product of a path and a star is less than or equal to 4. In this work, (1) We give an appropriate decomposition of trees. (2) We give an upper bound of the basis number of a cycle and a bipartite graph. (3) We give an upper bound of the basis number of a path and a bipartite graph. This is a generalization of Ali's result [3].