On the Independence Number of the Modular Product

Abstract

The \emph{modular product} $G\diamond H$ of graphs $G$ and $H$ is a graph on vertex set $V(G)\times V(H)$. Two vertices $(g,h)$ and $(g^{\prime },h^{\prime })$ of $G\diamond H$ are adjacent if $g=g^{\prime }$ and $h{h}^{\prime }\in E(H)$, or $g{g}^{\prime }\in E(G)$ and $h=h^{\prime }$, or $g{g}^{\prime }\in E(G)$ and $h{h}^{\prime }\in E(H)$, or (for $g\ne g^{\prime }$ and $h\ne h^{\prime }$) $g{g}^{\prime }\notin E(G)$ and $h{h}^{\prime }\notin E(H)$. The independence number $\alpha (G)$ of a graph $G$ is the maximum cardinality of a set of pairwise nonadjacent vertices in $G$. In this paper, we study the independence number of the modular product of graphs. We first structurally characterize all independent set of $G\diamond H$ which lead to the exact result on $\alpha (G\diamond H)$. Special cases of this result lead to several sharp bounds and some exact results for $\alpha (G\diamond H)$. Finally, we introduce a partition graph associated with $G\diamond H$ that provides a framework for constructing independent sets of the modular product from independent sets of its substructures.

19 pages, two figures, 26 references