FoCM 2014 conference
Workshop A4 - Graph Theory and Combinatorics
December 11, 17:00 ~ 17:30 - Room B11
Toughness and Kronecker product of graphs
Daniel A Jaume
Universidad Nacional de San Luis, Argentina - djaume@unsl.edu.ar
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)
What is the number of elements that are not functioning?
What is the number of remaining connected subnetworks (graphs)?
What is the size of a largest remaining group within mutual communication can still occur (the size of a largest remaining connected component)?
Many graph theoretical parameters such as connectivity, toughness, scattering number, integrity, tenacity, rupture degree, and their edge-analogues, have been defined to obtain the answers to these questions. These parameters have been used to measure the vulnerability of a graph (network)
For most of these parameters, the corresponding computing problems are NP-hard. In this work we generalized a result of Mamut and Vumar, for the toughness of Kronecker product of graphs (Vertex vulnerability parameters of Kronecker products of complete graphs, Information Processing letters 106 (2008) 258-262):
Theorem: Let $G$ be a graph with $t(G)\geq n\geq 3$, then $t(G\times K_n)=n-1$
Joint work with Adrián Pastine (Michigan Technological University).