论文标题
Mycielskian的G-Extra连接性
The g-extra connectivity of the Mycielskian
论文作者
论文摘要
$ g $ -EXTRA连接是衡量互连网络的公差和可靠性能力的重要参数。给定连接的图$ g =（v，e）$和非负整数$ g $，如果断开$ g-s $的$ g $ g-s $ cubset $ s \ subseteq v $，则称为$ g $ extra削减$ g-s $，并且$ g-s $的每个组成部分至少都有$ g+1 $ g+1 $ $ 1 $ $ g+1 $。最低$ G $ -EXTRA削减的基数定义为$ g $ g $的$ g $ - extra连接性，由$κ_g（g）$表示。在搜索具有任意大色数的无三角形图时，Mycielski开发了一个图形转换，将图$ G $转换为新的图$μ（g）$，这称为$ g $的mycielskian。本文研究了Mycielskian $μ（G）$和Graph $ G $的G-Extra连接性的关系，此外，表明$κ__{2G+1}（μ（g））=2κ__{G}（G}（G） \ lfloor \ frac {n} {2} \ rfloor \} $。
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\}$.
