Vulnerability parameters of tensor product of complete equipartite graphs

P. Paulraja
V. Sheeba Agnes

Abstract. Let \(G_{1}\) and \(G_{2}\) be two simple graphs. The tensor product of \(G_{1}\) and \(G_{2}\), denoted by \(G_{1}\times G_{2}\), has vertex set \(V(G_{1}\times G_{2})=V(G_{1})\times V(G_{2})\) and edge set \(E(G_{1}\times G_{2})=\{(u_{1},v_{1})(u_{2},v_{2}):u_{1}u_{2}\in E(G_{1})\) and \(v_{1}v_{2}\in E(G_{2})\}\). In this paper, we determine vulnerability parameters such as toughness, scattering number, integrity and tenacity of the tensor product of the graphs \(K_{r(s)}\times K_{m(n)}\) for \(r\geq 3, m\geq 3, s\geq 1\) and \(n\geq 1,\) where \(K_{r(s)}\) denotes the complete \(r\)-partite graph in which each part has \(s\) vertices. Using the results obtained here the theorems proved in [Aygul Mamut, Elkin Vumar, Vertex Vulnerability Parameters of Kronecker Products of Complete Graphs, Information Processing Letters 106 (2008), 258-262] are obtained as corollaries.

Keywords: fault tolerance, tensor product, vulnerability parameters.

Mathematics Subject Classification: 05C76, 05C40.

Full text (pdf)