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_1{x}_2\in E(G_1),y_1{y}_2\in E(G_2)\}$. Very recently, Zhang, Zheng, and Mamut showed that if $\delta (G_1)\ge 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)\ge 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\le \delta (G)\le \mathrm{\Delta }(G)\le 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$.