Toughness and Kronecker product of graphs

DANIEL A JAUME

Montevideo

Conferencia; Foundations of Computational Mathematics conference 2013; 2014

Society for Foundations of Computational Mathematics

When investigating the vulnerability of a communication network (graph) to disruption, one may want to find the answer of the following questions (there may be others) \cite{b1}: \begin{enumerate} \item What is the number of elements that are not functioning? \item What is the number of remaining connected subnetworks (graphs)? \item What is the size of a largest remaining group within mutual communication can still occur (the size of a largest remaining connected component)? \end{enumerate} Many graph theoretical parameters such as connectivity \cite{b2}, toughness \cite{b3}, scattering number \cite{b4}, integrity \cite{b2}, tenacity \cite{b5}, rupture degree \cite{b6}, and their edge-analogues, have been defined to obtain the answers to these questions. In other words, these parameters have been used to measure the vulnerability of a network (graph)\\ For most of these parameters, the corresponding computing problems are NP-hard. In this work we generalized a result of Mamut and Vumar \cite{b7} for the toughness of Kronecker product of graphs.\\ Theorem: Let G be a graph with $t(G)\geq n\geq 3$, then $t(G\times K_n)=n-1$ %Bibliografía \begin{thebibliography}{9} \bibitem{b1} C. A. Barefoot, R. Entriger and H. Swart, \textit{Vulnerability in graphs: a comparative survey}, J. Combin. Math. Combin. Comput. 1 (1987), 13-22. \bibitem{b2} G. Chartrand and L. Lesniak \textit{Graphs \& Digraphs}, 3rd. edition. Chapman \& Hall. 1996. \bibitem{b3} V. Chvátal, \textit{Tough graphs and Hamiltonian circuits}, Discrete Math. 5 (1973), 215-228. \bibitem{b4} H. A. jung, \textit{On a class of posets and the corresponding comparability graphs}, J. Combinatorial Theory Sr. B 24 (1978), no. 2, 125-133. \bibitem{b5} M. Cozzen, D. Moazzami and S. Stueckele, \textit{The tenacity of a graph}, in Graph theory, combinatorics, and algorithms. Vol. 1,2 (Kalamazoo, MI 1992), 1111-1122, Wiley, New York. \bibitem{b6} Y. Li, S. Zhang and X. Li, \textit{Rupture degree of graphs}, Int. J. Comput. Math. 82 (2005), n0. 7, 793-803. \bibitem{b7} A. Mamut and E. Vumar, \textit{Vertex vulnerability parameters of Kronecker products of complete graphs}, Information Processing letters 106 (2008) 258-262. \end{thebibliography}