Toughness of Kronecker Product of Graphs

Abstract

The toughness $t(G)$ of a noncomplete graph $G$ is defined as $$t(G)=min\{\frac{|S|}{w(G–S)}\mid S\subset V(G),w(G–S)\ge 2\}$$ and the toughness of a complete graph is $\mathrm{\infty }$, where $w(G–S)$ is the number of connected components of $G–S$. In this paper, we give the sharp upper and lower bounds for the Kronecker product of a complete graph and a tree. Moreover, we determine the toughness of the Kronecker product of a complete graph and a star, a path, respectively.