The g-extra connectivity of the Mycielskian

Abstract

The $g$-extra connectivity is an important parameter to measure the ability of tolerance and reliability of interconnection networks. Given a connected graph $G=(V,E)$ and a non-negative integer $g$, a subset $S\subseteq V$ is called a $g$-extra cut of $G$ if $G-S$ is disconnected and every component of $G-S$ has at least $g+1$ vertices. The cardinality of the minimum $g$-extra cut is defined as the $g$-extra connectivity of $G$, denoted by ${\kappa }_g(G)$. In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph $G$ into a new graph $\mu (G)$, which is called the Mycielskian of $G$. This paper investigates the relationship of the g-extra connectivity of the Mycielskian $\mu (G)$ and the graph $G$, moreover, show that ${\kappa }_{2g+1}(\mu (G))=2{\kappa }_g(G)+1$ for $g\ge 1$ and ${\kappa }_g(G)\le min\{g+1,\lfloor \frac{n}{2}\rfloor \}$.