一致超图的边连通性和最大边连通性

张磊，牛倩楠，任海珍

（青海师范大学 数学与统计学院，青海 西宁 810008）

0 引言

近年来，作为图的推广，超图已经得到了广泛而深入的研究，并且经常被作为一种成功的工具来表示离散数学、计算机科学等领域中的结构。特别地，作为一个处理计算机科学中出现的特定问题的方法，超图通常用于建立网络模型，这些网络含两个或更多处理器之间的通信链接。在超图中，存在一个与网络容错性相关的基本参数，即：边连通度。边连通度是网络可靠性的经典度量，边连通度越大，则网络可靠性越强。关于图和有向图的边连通度已有很多结果。如，Chartrand［1］证明如果图G的阶数为p，且其最小度至少为，则G的边连通度等于G的最小度；Lesniak［2］证明如果图G的阶数p≥2，并且对于所有不相邻的顶点u和v满足d(u)+d(v)≥p—1，则G的边连通度等于G的最小度。此外，Goldsmith［3］给出了图的边连通度等于其最小度的一个充分条件；Harary［4］获得了图的边连通度、最小度和连通度之间的关系，即：κ≤λ≤δ；Plesnik［5］表明：如果图G的直径D(G)≤2，则图G的边连通度等于它的最小度。Znam［6］放宽了Plesnik［5］中的条件，使其在直径D(G)＞2时也可以获得相应的结果。近年来，人们把目光也转向了超图边连通性的研究。Zykov［7］获得了超图的Menger型定理；Cheng［8］研究了超图中边连通度增加1所需的最小边数的Min-Max关系；Gu等［9］得到了有关k边连通一致超图度序列的一个充要条件；Dankelman等［10］将图的最大边连通的一些众所周知的充分条件推广到超图；Zhao等［11］给出了超图最大边连通性的一个充分条件。通过图的固定图不变量来刻画图的结构性质是图理论研究的一个热点。在图（有向图）的边连通度方面，Esfahanianc［12］利用图参数给出了图的边连通度的一个下界；Imase［13］利用有向图的图参数获得了有向图的边连通度的一个下界。本文致力于利用超图的图参数来刻画其边连通度。主要借助r-一致超图的最大度和直径给出了其边连通度的一个下界。特别地，当r-一致超图的直径D小于等于2时，利用其最大度给出了其边连通度的一个下界。进一步地，得到了r-一致超图是最大边连通的一个充分条件。

1 定义和符号

一个超图H(V，E)是一个有序对，其中V是H的顶点集，E是H的边集，边集中的元素都是顶点集的非空子集。如果一个超图H的每条边都是一个含有r个元素的集合，则称超图H是r-一致的。一个2-一致超图就是一个简单图。如果e是超图H的一条边，且e包含顶点v，则称顶点v与边e关联。如果超图H中有一条边包含H中的两个不同的顶点，则称这两个顶点是邻接的。顶点u的邻域N(u)指的是在超图H中与u邻接的所有顶点的集合。对于任意的顶点v∈H，Iv定义为超图H中与顶点v关联的所有边集的集合。超图H中任意的顶点v的度，最小度和最大度分别记作d(v)＝|Iv|，δ(H)＝min{d(v)|v∈V}，Δ(H)＝max{d(v)|v∈V}。一个超图H中的游走W是一个有限交错序列W＝(v0，e1，v1，e2，…，ek，vk)，其中vi是顶点，ej是边，i＝0，1，…，k；j＝1，2，…，k。一个游走W是一条路径，如果在W中的所有顶点vi互不相同且所有边ej也互不相同，其中i＝0，1，…，k；j＝1，2，…，k。一对不同顶点u和v之间最短路径的长度由L(u，v)表示。令L(u，X)＝min{L(u，v)|v∈X}，其中X⊂V，u∈V—X。超图H的直径D(H)定义为D(H)＝max{L(u，v)|u，v∈V}，其中u和v是无序的顶点对。对于超图H边集的一个非空子集S，H—S定义为H中删去S中所有边得到的超图。如果在超图H的任何一对顶点之间存在游走，则这个超图是连通的。在本文中，我们只考虑连通简单超图，即：如果i＝j，那么ei＝ej。图的边连通度可以很自然的推广到超图，定义如下。

定义1对于超图H的边集E的一个非空子集S，如果H—S是不连通的，则S是H的一个边割。一个超图H的边连通度λ(H)定义为超图H的所有边割中最小边割的大小。

2 主要结果

设H(V，E)表示一个连通的简单r-一致超图，其中，顶点数|V(H)|＝n，边数|E(H)|＝m。令S为r-一致超图H的一个最小边割，它的顶点集为V(S)。因为S是H的最小边割，所以H—S的连通分支的个数是ω满足2≤ω≤r。用X1，X2，…，Xω表示H—S的ω（2≤ω≤r）个连通分支的顶点集。众所周知，λ(H)≤δ(H)。更进一步，令U1⊆X1∩V(S)，U2⊆X2∩V(S)，…，Uω⊆Xω∩V(S)。注意1≤|Ui|≤λ(H)(1≤i≤ω)。下面先讨论λ(H)＜δ(H)的情况，在证明主要结果之前还需要以下引理。