Menu
A graph is said \(h\)-decomposable if its edge-set is decomposable into hamiltonian cycles. In this paper, we prove that if \(G = L_1 \cup L_2 \cup L_3\) is a strongly hamiltonian bipartite cubic graph (where \(L_i\) is a perfect matching, for \(1 \leq i \leq 3\) and \((L_1, L_2, L_3)\) is a \(1\)-factorization of \(G\)), then \(G \times C_{2n+1}\) (where \(n\) is odd and \(n \geq 1\)) is decomposable. As a corollary, we show that for \(r \geq 1\) odd and \(n \geq 3\), \(K_{r,r} \times K_n\) is \(h\)-decomposable. Moreover, in the case where \(G\) is a strongly hamiltonian non-bipartite cubic graph, we prove that the same result can be derived using a special perfect matching. Hence \(K_{2r} \times K_{2n+1}\) will be \(h\)-decomposable, for \(r,n \geq 1\).
To study the product of \(G = L_1 \cup L_2 \cup L_3\) by even cycle, we define a dual graph \(G_C\) based on an alternating cycle subset of \(L_2 \cup L_3\). We show that if a non-bipartite cubic graph \(G = L_1 \cup L_2 \cup L_3\), with \(|V(G)| = 2m\), admits \(L_1 \cup L_2\) as a hamiltonian cycle and \(G_C\) is connected, then \(G \times K_2\) is hamiltonian and \(G \times C_{2n}\) has two edge-disjoint hamiltonian cycles. Finally, we prove that if \(C = L_2 \cup L_3\) and \(L_1 \cup L_3\) admits a particular alternating \(4\)-cycle \(C’\), then \(G \times C_{2n}\) is \(h\)-decomposable.