极大3等周边连通图的充分条件

徐子钧,张磊

(晋中学院数学学院, 山西 晋中 030600)



极大3等周边连通图的充分条件

徐子钧,张磊*

(晋中学院数学学院, 山西 晋中 030600)

摘要：k等周边连通度是一个比边连通度更可靠的网络可靠性参数。 连通图G的k等周边连通度定义为:X⊆≥k},其中=V(G)X。令:X⊆=k}。图G是极大k等周边连通的如果γk(G)=βk(G)。令G是一个阶至少为6的连通图。本文证明了如果对于G中任意一对不相邻的顶点u,v,当u和v都不在三角形中时满足≥2;当u和v中至少有一个在三角形中时满足≥5,那么G是极大3等周边连通的。

关键词：互连网络;极大k等周边连通图;k等周边连通度;邻域

1　引言

定义1.1设k是一个正整数,G是一个阶至少为2k的连通图。G的k等周边连通度定义为:

令

显然,γk(G)≤βk(G)。 2007年,Zhang等[8]给出了极大k等周边连通图的定义。

定义1.2设k是一个正整数, G是一个阶υ≥2k的连通图。如果γk(G)=βk(G), 那么称G是极大k等周边连通的。

2009年,Wang等[9]给出了一个极大k等周边图的邻域条件。

定理1.4[9]设k是一个正整数, G是一个阶至少为2k的图。如果对G中任意两个不相邻顶点u,v都有

那么G是极大k等周边连通图。

本文将给出极大3等周边连通图的邻域条件, 这个结果在k=3时, 改进了定理1.4。

2　主要结论

(1)如果在X中存在一个基数为k的子集U使得

那么G是极大k等周边连通的。

(2)X中不存在基数为k的子集U使得

定理2.2设G是一个阶至少为6的连通图。如果对于G中任意不相邻的顶点u和v,当u,v都不在三角形中时，满足

当u,v至少有一个在三角形中时，满足

那么G是极大3等周边连通的。

=0。

由引理2.1(1)知,G是极大3等周边连通的。

由引理2.1(1)知,G是极大3等周边连通的。……