The Basis Number of the Lexicographic Product of Graphs

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 \quad \forall n,m \geq 7,\]
\[b(C_n \otimes P_m) = b(C_n \otimes C_m) = 4 \quad \forall n,m \geq 6,\]
\[b(P_n \otimes W_m) = 4 \quad \forall n,m \geq 9,\]
and
\[b(C_n \otimes W_n) = 4 \quad \forall n,m \geq 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\).