Nowhere-zero \(3\)-flows in Tensor Products of Graphs

Abstract

The tensor product of two graphs \(G_1\) and \(G_2\), denoted by \(G_1 \times G_2\), is defined as the graph with vertex set \(\{(x, y): x \in V(G_1), y \in V(G_2)\}\) and edge set \(\{(x_1, y_1)(x_2, y_2): x_1x_2 \in E(G_1), y_1y_2 \in E(G_2)\}\). Very recently, Zhang, Zheng, and Mamut showed that if \(\delta(G_1) \geq 2\) and \(G_2\) does not belong to a well-characterized class \(\mathcal{G}\) of graphs, then \(G_1 \times G_2\) admits a nowhere-zero \(3\)-flow. However, it remains unclear whether \(G_1 \times G_2\) admits a nowhere-zero \(3\)-flow if \(\delta(G_1) \geq 2\) and \(G_2\) belongs to \(\mathcal{G}\), especially for the simplest case \(G_2 = K_2\). The main objective of this paper is to show that for any graph \(G\) with \(2 \leq \delta(G) \leq \Delta(G) \leq 3\), \(G \times K_2\) admits a nowhere-zero \(3\)-flow if and only if either every cycle in \(G\) contains an even number of vertices of degree \(2\) or every cycle in \(G\) contains an even number of vertices of degree \(3\). We also extend the sufficiency of this result to graphs \(G \times K_2\), where all odd vertices in \(G\) are of degree \(3\).