点积图的超连通性(英文)

Super Connectivity of Dotgraphs

如果图G的每个极小点割(边割)都孤立一个点,则图G是超点连通(超边连通)的。图G的至少孤立一条边的边割称为限制性边割,其最小基数计作λ′(G)。当λ′(G)=ξ(G)时,称图G是λ′-最优,其中ξ(G)是图G的最小边度。本文给出了点积图是超点连通、超边连通、的一些充分条件。

A graph G is super-κ（super-λ ） if every minimum vertex-eut（edge-cut） isolates a vertex of G. An edge set S is called a restricted edge-cut of G if G-S is disconnected without isolated vertices. Denote by λ′（G） the eardinality of a minimum restricted edge-cut.Then λ′ （G） ≤ ξ（G） ,where ξ（G） is the minimum edge degree of G. If λ′（G） = ξ（G） ,then G is called λ′-optimal. In this paper,we give some sufficient conditions for a dotgraph to be super-κ,super-λ ,and λ′-optimal.