广义Mycielskian图的超连通性

Super Connectivity of the Generalized Mycielskian Graphs

Mycielski引入了对于图G的一类新的变换图μ(G),称为G的Mycielskian.这类变换图的推广是广义Mycielskian图μm(G),m是正整数.如果每个最小点割(最小边割)孤立G的一个点,则称图G是超连通的或超-κ(超边连通的或超-λ).证明结果显示:设G是连通图且︱V(G)︱≥3条件下,μm(G)是超-κ的充要条件是δ(G)<(m+1)κ(G);μm(G)是超-λ的充要条件是G■K2,即G不是一条边.

Abstract： Mycielski introduced Ix（G） , a graph transformation for graph G, or the MycleisKlan ot t~. generalization of this transformation is the generalized MycielskianIx,（G） , where is a positive integer. A graph is super-connected or simply super - s：（ resp. super edge connected or super-A）, if every minimum vertex cut （resp. minimum edge cut） isolates a vertex of G. In this paper, it is shown that for a connected graph G with IV（G） ≥ 3,μm（G） is super-K if and only ifS（G） 〈 （m ＋ 1）s：（G） , andtμm（G） is super-A if and only if G K2, that is, G is not an edge.