应用研究
二连通三正则网络的直径
林馨
(福建师范大学数学与计算机科学学院福建福州350007)
与皮
摘要：网络的直径是衡量网络交互有效性的一个重要参数。Ore给出了无向网络直径的上界。本文将在此基础上讨论2一连通三正则网络的直径的上界
关键词：直径三正则二连通
中图分类号：0157.5 1引言
文献标识码:A
网络的直径是衡量网络交互有效性的一个重要参数。对于这方面的研究,Ore以及Chung等给出了不少成果。其中Ore给出了一个无向网络G的边数E（G）的上界。我们把一个网络称为(n,d)-graph如果它是n阶的并具有直径dOre的定理如下：
定理1.对任意连通的无向网络(n,d)-graphG， IE(G)≤ d +(n d + 4)(n d 1)
3n
对任意n阶2-连通三正则网络G，IE(G)=
。因此由定理1，我 2
们可以得到d≤n+
-V4n+17。本文将证明任意n阶2-连通三正则
网络直径的上界为号-1。由于当凸≥7时，号
n_1≤n+
2
于2一连通三正则网络，我们将改进Ore的结论。 2主要结论
/4n+17,对
我们将网络抽象为图以进行研究。以下涉及到的图论中常用符号和概念参见"
定义1.令H为n则哈密尔正则图的集合。J为n阶2-连通三正则图的集合。
定义2.对veV(G)，我们记deg(v)为V在G中的度数。令 d(G)=max(d(u,v)，其中d(u,v)表示u，V之间的距离。令 d(max, S) =max d(G),
定理2.d(max,H)="-1
2
证明，显然有n是偶数且d(max,H)="，
。假设存在GeH，使得
.令C为G中的哈密尔顿圈并记C)。不失 d(G)=:
"，则不存在"EV(G)使得
般性我们假设d(%,V)=
<，与e）-3矛盾。因此
"E(G)E(C），否则d(")
文章编号：1007-9416(2013)06-0120-01
d(max,H)≤号-1。令H(n)为n阶三正则图满足： V(H(n)) = (va.V...-,V..)
E(H(n) = (v :/=,I,.,1(mod n) U(V-3 42
d(H(n)= d(ve,v,): 定理3.d(max,J)=
2
-1得d(mt, H)=号
。假设存在GeJ满足d(G)=
证明.显然有d(max,J)≤
号。由定
理1可知G不是哈密尔顿图。假设d(u,)="
兰其中u,veV(G)。因为G
为2一连通，所以u，V两点有内部不交的两条路P,P相连。于是 Id(u,v)=且[d(u,V)=
。因此PP是G的一个哈密尔顿
图，得到矛盾。因此d(max,J)≤-1。由HcJ且d(max,H)≤d(max,J)
得d(max, J)=兰-1。 3结语
本文给出了2连通三正则网络的直径的上界，为研究网络交互
的有效性提供了基础。参考文献
soeode o de.n sn pe pog c 1st Edition, The MacMillan Press, 1976,
[2JChung. Diameters of communication networks, Proceeding of Symposia in App1ied Mathematics, 1986, 34:118.
[3JOre. 0, Diameter in Graphs, Journal of Combinatorial Theory. 1986, 5: 7581