The basis number of the strong product of paths and cycles with bipartite graphs. (English) Zbl 1146.05031

Jaradat, M. M. M.

Missouri J. Math. Sci. 19, No. 3, 219-230 (2007).

Summary: The basis number of a graph \(G\) is defined to be the least integer \(d\) such that there is a basis \({\mathcal B}\) of the cycle space of \(G\) such that each edge of \(G\) is contained in at most \(d\) members of \({\mathcal B}\). S. MacLane [Fundam. Math. 28, 22–32 (1937; Zbl 0015.37501)] proved that a graph \(G\) is planar if and only if the basis number of \(G\) is less than or equal to 2. Ali [A. A. Ali and G. T. Marongi, The basis number of the strong product of graphs, Mu’tah Lil-Buhooth Wa Al-Pirasat 7, 211–222 (1992)] 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 [loc. cit.].

MSC:

05C38	Paths and cycles
05C75	Structural characterization of families of graphs

Citations:

Zbl 0015.37501