Equality in Vizing’s Conjecture Fixing One Factor of the Cartesian Product

Abstract

In this paper, we investigate the existence of nontrivial solutions for the equation \(y(G \Box H) – \gamma(G) \gamma(H)\) fixing one factor. For the complete bipartite graphs \(K_{m,n}\), we characterize all nontrivial solutions when \(m = 2, n \geq 3\) and prove the nonexistence of solutions when \(m \geq 2, n \leq 3\). In addition, it is proved that the above equation has no nontrivial solution if \(A\) is one of the graphs obtained from \(G\), the cycle of length \(n\), either by adding a vertex and one pendant edge joining this vertex to any vertex to any \(v\in V(C_n)\), or by adding one chord joining two alternating vertices of \(C_n\).