The g-extra connectivity of the Mycielskian

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 $κ_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 $μ(G)$, which is called the Mycielskian of $G$. This paper investigates the relationship of the g-extra connectivity of the Mycielskian $μ(G)$ and the graph $G$, moreover, show that $κ_{2g+1}(μ(G))=2κ_{g}(G)+1$ for $g\geq 1$ and $κ_{g}(G)\leq min\{g+1, \lfloor\frac{n}{2}\rfloor\}$.

No reviews yet.

No comments yet.