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\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}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\ge 3$ and prove the nonexistence of solutions when $m\ge 2,n\le 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$.