Independent Sets and Matchings in Tensor Product of Graphs

Abstract

Let $\alpha (G)$ and $\tau (G)$ denote the independence number and matching number of a graph $G$, respectively. The tensor product of graphs $G$ and $H$ is denoted by $G\times H$. Let $\underset{\_}{\alpha }(G\times H)=max\{\alpha (G)\cdot n(H),\alpha (H)\cdot n(G)\}$ and $\underset{\_}{\tau }(G\times H)=2\tau (G)\cdot \tau (H)$, where $\nu (G)$ denotes the number of vertices of $G$. It is easy to see that $\alpha (G\times H)\ge \underset{\_}{\alpha }(G\times H)$ and $\beta (G\times H)\ge \underset{\_}{\tau }(G\times H)$. Several sufficient conditions for $\alpha (G\times H)>\underset{\_}{\alpha }(G\times H)$ are established. Further, a characterization is established for $\alpha (G\times H)=\underset{\_}{\tau }(G\times H)$. We have also obtained a necessary condition for $\alpha (G\times H)=\underset{\_}{\alpha }(G\times H)$. Moreover, it is shown that neither the hamiltonicity of both $G$ and $H$ nor large connectivity of both $G$ and $H$ can guarantee the equality of $\alpha (G\times H)$ and $\underset{\_}{\alpha }(G\times H)$.