广义Petersen图的直径.ppt

广义Petersen图的直径 刘焕平1 周树娜2 1(哈尔滨师范大学数学科学学院) 2(内蒙古大学满洲里分校) 广义Petersen图自从1950年提出以来, 就引起了许多研究者的兴趣. 但是由于广义Petersen图p(m,a)的直径依赖于a, 随着a的增大图的结构会不断的复杂化, 目前还没有找到p(m,a)通用的直径表达式. 对a=2时广义Petersen图的直径、宽直径、容错直径等参数有很多人进行了研究, 其中在1987年Krishnamoorthy 和Krishnamurthy给出了m为奇数时 p(m,2)的直径. 2004年侯新民、王天明两人完善了这个结果，对任意m给出了p(m,2)的直径. 在本文中,我们将给出p(m,2)的直径. 定义 广义Petersen图记为p(m,a), 其中a<m/2, m和a均为正整数. 它的顶点集定义为U∪W, 其中U={u0 , …,um-1 },W={w0 , …,wm-1}.将U中的元素称为外圈点, W中的元素称为内圈点; 边集为E={ui wi , ui ui+1, wiwi+a :0≤i≤m-1},称ui wi为对应边,称wiwi+a为内圈边, 称ui ui+1为外圈边, 下标为模m的运算. 定理1　在p(m,3)中, 对任意一个外圈点ui(3≤i≤m-3), 一定存在一条经过内圈点wi的最短的u0ui路, 并且wi ui是这条路上的最后一条边. 定理4　当m>7时, p(m,3)的直径可表示成下面的形式： 当m≡0(mod 3)时, 当m≡1(mod 3) 时, 当m≡2(mod 3)时, Thanks very much 情形二：i≡1(mod 3)，此时可找到一条最短的u0ui路 证明：只考察 的情形，其它情形类似。 情形一：i≡0(mod 3)，此时可找到一条最短的u0ui路 情形三：i≡2(mod 3) 3.1 m为偶数且m≡2(mod 3)， ，此时可找到一条最短的u0ui路 3.2 否则，可以找到一条最短的u0ui路 定理2　 p(m,3)的直径不能在一个外圈点和一个内圈点的距离达到. 证明　假设达到直径的两个点, 一个是外圈点,另一个是内圈点. 由于p(m,3)的对称性, 不妨设外圈点为u0, 内圈点设为wi, 设p为到的一条最短路, 由定理1知, 存在一条u0到ui的最短路p,它是由一条u0 wi路与wi ui直接相连得到的. 根据两点距离的定义于可知：d(u0 , wi)< d(u0 , ui) , 这与直径的定义矛盾. 因此假设不成立. 定理3　在p(m,3) 中至少能找到两对点: 一对点同在外圈,设为ui ,uj, 另一对点同在内圈,设为wk ,wt, 使得有 d(ui ,uj )= d(wk ,wt)=d 成立. 其中m>7, 0≤i<j≤m-1, 0≤k<t≤m-1, d为p(m,3)的直径. 证明　由定理2知，达到p(m,3)直径的两个点, 要么同在内圈，要么同在外圈。下面只需证明当外圈任意两点的最短路p确定时, 在内圈上也能找到两点使得它们的最短路的路长与|p|相等; 反之当内圈两任意点的最短路p′确定时, 在外圈上也能找到两点使得它们的最短路的路长与|p′|相等. 下面只对前一部分加以证明, 后一部分可类似证明. 不失一般性, 在外圈上任意固定一个点设为u0, 另一个点设为ui.下面我们只讨论 时的情形（其它情形可类似证明）： 情形一：i≡0(mod 3)，此时可找到一条最短的u0ui路 1.1 m≡0(mod 3)，此时可找到两个内圈点w0，wi-2及其一条最短的w0wi-2路，其路长等于|p1|. 1.2 m≡1(mod 3)，此时可找到两个内圈点w0，wi-4及其一条最短的w0wi-4路, 其路长等于|p1|. 1.3 m≡2(mod 3)，同上可找到两个内圈点w0，wi-4及其一条最短的w0wi-4路, 其路长等于|p1|. 情形二：i≡0(mod 3)，此时可找到一条最短的u0ui路 1.1 m≡0或2(mod 3)，此时可找到两个内圈点w0，wi及其一条最短路，其路长等于|p1|. 1.2 m≡1(mod 3)，此时可找到两个内圈点w0，wi-2及其一条最短路, 其路长等于|p1|. 情形三：i≡2(mod 3) ，分两种子情形来讨论 1.1 m≡0或1(mod 3)，此时u0ui最短路的长度为(i+ 10)/3, 同时可找到两个内圈点w0，wi及其一条最短路，其路长也等于(i+ 10)/3. 1.2 m≡2(mod 3) 若m为偶数，且恰有