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 \(\underline{\alpha}(G \times H) = \max \{\alpha(G) \cdot n(H), \alpha(H) \cdot n(G)\}\) and \(\underline{\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) \geq \underline{\alpha}(G \times H)\) and \(\beta(G \times H) \geq \underline{\tau}(G \times H)\). Several sufficient conditions for \(\alpha(G \times H) > \underline{\alpha}(G \times H)\) are established. Further, a characterization is established for \(\alpha(G \times H) = \underline{\tau}(G \times H)\). We have also obtained a necessary condition for \(\alpha(G \times H) = \underline{\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 \(\underline{\alpha}(G \times H)\).