The Basis Number of the Lexicographic Product of Graphs

Abstract

We define the basis number, $b(G)$, of a graph $G$ to be the least integer $k$ such that $G$ has a $k$-fold basis for its cycle space. We investigate the basis number of the lexicographic product of paths, cycles, and wheels. It is proved that

$$b(P_n\otimes P_m)=b(P_n\otimes C_m)=4\mathrm{\forall }n,m\ge 7,$$
$$b(C_n\otimes P_m)=b(C_n\otimes C_m)=4\mathrm{\forall }n,m\ge 6,$$
$$b(P_n\otimes W_m)=4\mathrm{\forall }n,m\ge 9,$$
and
$$b(C_n\otimes W_n)=4\mathrm{\forall }n,m\ge 8.$$

It is also shown that $max\{4,b(G)+2\}$ is an upper bound for $b(P_n\otimes G)$ and $b(C_n\otimes G)$ for every semi-hamiltonian graph $G$.