定向完全分裂图的最小有向直径

定向完全分裂图的最小有向直径 ( ) 文章编号 : 1004 - 1478 2008 02 - 0110 - 04 定向完全分裂图的最小有向直径 王培 () 中国石油大学 数理系 , 北京 102249 摘要 :研究了完全分裂图所有定向中的最小有向直径 ,并得出如下结论 : 如果 | X | = m , | Y | = n, 那么 m m ( ) n ?时 , 完全分裂图的最小有向直径是 3; 当 n ?- g m 时 , 其最小有向直径是当 Lm / 2 」 Lm / 2 」 () 2, 其中 m , n ?5, g m 是一个已知函数. 关键词 :完全分裂图 ;有向图 ;有向直径 中图分类号 : O 157. 5文献标志码 : A M in im um d irec ted d iam e ter of or ien ta t ion s of com p le te sp ilt gra ph WAN G Pe i ()D ept. of M a the. and Physics, Ch ina U n iv. of Petroleum , B eijing 102249, Ch ina A b stra c t: The m in im um d irec ted d iam e te r of o rien ta tion s of the comp le te sp lit grap h wa s con side red. Fo r the comp le te sp lit grap h Sw ith m , n ?5 , it is shown tha t the m in im um d irec ted d iam e te r of o rien ta tion s m , n m m () () of Sis 3 fo r n ? , and 2 fo r n ? - g m , whe re g m is a given in tege r func tion.m , n Lm / 2 」Lm / 2 」 Key word s: comp le te sp ilt grap h; d igrap h; d irec ted d iam e te r 不在同一子集的所有顶点均相邻. 完全二部图则用 0 引言K表示. m , n [ 1 ] 设 D 是一个有向图 , u, v是 D 的 2个不同顶点 , ( ) 图 G 称为分裂图 , 是指 G 的顶点集 V G 可 ( ) () ( )用 u ?v表示 u, v?A D , d u, v表示从 u 到 v的 以分解为 2个子集 X , Y, 其中 X 导出的子图是一个 ( ) 距离 , 即 D 中的最短有向 u, v- 路的长度 , 如果 u, 团 , Y 是独立集. 分裂图可以看作是介于二部图和其 [ 2 ] ( ) v之间没有有向路 , 则 d u, v= ?. D 的有向直径是 补图之间的一类图. Fo lde s等 首次对分裂图进行 指从 D 的任一顶点到任何别的顶点的最大距离 , 即 了研究. 在分裂图 G 中 , 如果 X 中的每个点都和 Y () ( ) () d iam D = m ax{ d u, v?u, v ?V D } () 设 U , W Α V D , 定义 U , W 之间的距离 中的每个点相邻 , 则称之为完全分裂图 , 用S表 m , n () ( ) d U , W = m ax{ d u, w ?u ?U , w ?W } ( ) } , Y =, x示 , 其中 V S= X ?Y, X = { x, x, m - 1 m , n 0 1 ( ) 对于一个图 G, 我们用 D G 表示 G 的一个定 ), m 表示完 k (, y,{ y, y}. 此外 , 用 K m , m , 0 1 n - 1 1 2 全 k 部图 , 它的点集可分解为 k 个子集 , 每个顶点与 收稿日期 : 2007 - 10 - 11 ( )基金项目 :天元数学基金项目 10726065 ( ) 作者简介 :王培 1979 —,女 ,河南省许昌市人 ,中国石油大学讲师 ,博士 ,主要研究方向 :运筹学控制论. 111??第 2期王 培 :定向完全分裂图的最小有向直径 ( ) 向 , 并称 G是 D G的基础图. G 的最小有向直径是对于 X 中的点 , 有如下情况 : )() 1 若 m ?1 mod2 , 当 0 ?i?m - 1时 , 有 指 G所有定向中的最小有向直径, 即 + ( ) (( ) ) ( ) ( )d iamG= m in{ d iam D G?D G是N x = { x, x, x,, x}m in X i i +1 i +3 i +5 i +m - 2 G的一个定向 } m )() 2 若 m ?2 mod4 , 当 0 ?i? - 1时 , 有[ 3 ] 2 对于完全二部图 K, Boe sch 等 了 , 如 m , n + m ( ) N x= { x, x, , x, X i i +1 i +3 i +- 2 果 m = n ?2, 则 K的最小有向直径是 3. P le sn ik进2 m , n[ 4 ] m m m 一步研究了 m ?n 的情况 , 证明了当 m , n ?2 时 , x, x, x,, x} i +i ++1 i ++3 i +m - 2 2 2 2 + [ 4 ] ( ) m = 6, N x= { x, x, x}. 若 K的最小有向直径不超过 4. 而 So lte s 则找到了 X i i + 1 i + 3 i + 4 m , n m ( ) d iamK的确切值 , 当 m ?n ?2 时 , 如果 m ?m in m , n 当?i?m - 1时 , 有 2 n , K的最小有向直径是 3; 否则 , 其值为 4.+ m , nm m m N( ) x={ x, x, , x, x, x,, x} Ln / 2 」X i i +1 i +3 i +- 2 i + +1 i + +3 i +m - 2 2 2 2 [ 5 ] + ( ) 1994年 , Gu tin研究了完全多部图的最小有向直 若 m = 6, N x = { x , x}. X i i + 1 i + 4 ) ( ) (径 , 证明了完全 k部图 K m , , m k ?3 的最小 1 k m )() 3 若 m ?0 mod4 , 当 0 ?i?- 1时 , 有2 有向直径不超过 3; 如果 m = = m = m , 除 n = 4, 1 k + m m m ( ) x, x, x,, x}, Nx={ x, x, i +- 1 i + +2 i + +4 i +m - 2 X i i +1 i +3 m = 1 的情况之外 , 它的最小有向直径是 2. 因为完2 2 2 m 全分裂图介于完全二部图和它的补图之间 , 而且也 当?i?m - 1时 , 有2 ( ,t是一个完全多部图 , 事实上 , S就是 K t, m m , n 1 + m m m () x ={ x , x , N, x , x , x , x , , x } Xi i +1 i +3 i+ - 1 i+ i+ +2 i + +4 i +m - 2 2 2 2 2 ) n , 其中 t= = t= 1, 所以对完全分裂图最小有 1 m m 这里的下标是指其模 m 之后的值. 由此可见 , 向直径研究非常有意义. 本文拟求得在大多数情况 + +() ( ) = Lm / 2 」, 而且 N x 对任意的 i,= N y X i i 下 S的最小有向直径的确切值.m , n ()Lm / 2 」或者 Lm / 2 」- 1. 此外 , 当 m ?2 mod4时 , 有 m 1 当 m , n ?5 时 , 如果 n ?, 则定理 + + m Lm / 2 」m = N[ x], 这里N( )0 ? i ? - 1; 当 m ?0 x X Xi + i 2 2 m ( ) ( ) -d iamS= 3; 如 果 n ? g m , 则m in m , n m+ + Lm / 2 」 m ()( ) ) mod4时 , 有 N x = N ( , 这里 0 ?i? x X i X i + + 1 2 2 ( ) d iamS= 2, 这里 m in m , n - 2. () 若 m ? 1 mod2 m 简单起见 , 在下文讨论有向图 D S时 , 使用下 m () g m = ()m / 2 若 m ? 2 mod4 面的符号 : ()m / 2 + 1 若 m ? 0 mod4 + + ( )if = Lm / 2 」 N x ( )x N i X Xi +( ) 对于图 G, 如果 V ′是 V G 的一个非空子集 , 则 N〈x〉= Xi ++= Lm / 2 」- 1 用 G [V ′]表示 G的由 V ′导出的子图. 对于有向图 D , N( ) if x ( )X N x i X i () 如果 V ′是 V D 的一个非空子集 , 则用 D [ V ′]表示 +N因此 , 对于 0 ?i?m - 1, 有 〈x〉 = Lm / 2 」. X i ( ) D 的由 V ′导出的有向子图. 对于 A Α A D , D \A 指 引理 1 当 m ?5时 , D S的有向直径等于 2. m 从 D 中删去 A 中的弧所得到的有向子图. 设 v ? + ( ) ( () ) V D , 则 v的外邻点集 N v= { u ?V - v?v, u 证明 设 y, y是 Y 中不同的 2 个点 , 由于 Y是i j - ( ) 独立集 , 所以 d y , y ?2. 根据 D S 的定向 , 有 ( ) ()() ?A D } , v的内邻点集 N v= { w ?V - v?w , vi m j + + - -+ + () ( ) ( ) ( ) ?A D } , 而且 N [ v ] = N v?{ v} , N [ v ] = N N y- N y?<, 那么存在点 x?X 使得 y? i j k i ) ( x?y, 所以 d y, y= 2. 类似地 , 对任意的 x, x?k j i j i j - + ( ) ( ) ( ) ( ) + + v?{ v}. 假设 W Α V D , 则 N v, N v分别W W ( ) ( ) ( ) ( ) - N x ?<, 则 d x , x ?2. 下 X i?j, N x Y i Y j i j + - + -( ) ( ) 表示 N v?W , N v?W , N [ v ] ?W , N [ v ] ( )( ) 面讨论 d X , Y 和 d Y, X . ?W. ( ) ( ) 情形 1 m ?1 mod2 而且 Lm / 2 」?1 mod2 . 易见 1 最小有向直径 ()Lm / 2」+2 ?j?m mod m x? x? y? x 0 Lm / 2」 j 0定义 S的一个定向图 D S为 m , m m x ? y ? x? x2 ? j ?Lm / 2 」+ 10 j 0 Lm / 2 」+1 + ( ) , x0 ? i ?m - 1N y= x, x, x? y? x? x i +Lm / 2 」- 1 i i i +1 0 1 2 0 ) ( 郑 州 轻 工 业 学 院 学 报 自 然 科 学 版 ?112?2008年 ( ) () 所以 , 对任意的 y?Y, 有 d x, y?2 而且 显然有 d iam D ′= 2. 如果 r?1, 那么 S中剩 j 0 j m , n 余的边定向为 ) ( ) ( d y, x?2. 根据 D S的对称性 , 可以得到 d X , Y j 0 m k ( ) ?2, d Y, X ?2.+ () N z= { x, x,, x}0 j0 j1 j, Ln / 2 」- 1 ( ) ( ) m ?1 mod2 而且 Lm / 2 」?0 mod2 . 情形 2 ??j = 1 易见( )( )Y \ { y, y} X ′\ { z} 0 0 1 ?()Lm / 2」+2 ?j?m mod m x? x? y? x 0 Lm / 2」+1 j 0 k 1 ? j ?Lm / 2 」 x? y? x? x0 j 0 + Lm / 2 」 ( ) N z= }, xi { x, x,j, i +Ln / 2 」- 1 ji j, i +1 ??x? y? x? x 0 m - 1 0Lm / 2 」+1j = 1 ( ) 因此 , 根据 D S的对称性 , 可以得到 d X , Y ? m ( ) ( )Y \ { y} X ′\ { z, z,, z} i i +1 0 1 ?( ) 2, d Y, X ?2. 这里 1 ?i?r - 1, 而且 x的第 2 个下标模为 n. j, l () 情形 3 m ?2 mod4 . 易见( )结合 D ′的定向 , 得到了 S的定向 D. 易见 d X , X m , n()Lm / 2」+2 ?j?m mod m x? y? y? x 0 Lm / 2」+1 j 0?2, 因为对于 0 ?i?r - 1, 有 1 ? j ?Lm / 2 」- 1x? y? x? x 0 j 0Lm / 2 」- 1 ()z? y? x? zLn / 2 」+ i?k ? n + i - 1 mod n i k 1 k i xx? x? y? x? y? x? x 00 1Lm / 2 」+1 0Lm / 2 」 m - 10 ()i +2 ?k ?Ln / 2 」+ i- 1 mod n 因此 , 根据 D S的结构和对称性 , 可以得到 z?y?x?z m i k 1, Ln / 2 」+ i i ) ( ) ( d X , Y ?2, d Y, X ?2.而且 () 情形 4 m ?0 mod4 . 易见z? z? y? zz? z? y? z 0 1 0 00 1 1 0 z? y? z? zz? x? y? z Lm / 2」+1 ?j?m x? x? y? x- 1 i i i - 1 ii 1 i i +1 i 0 Lm / 2」- 1 j 0 ? y? x? x2 ? j ?Lm / 2 」 x j 0 0 Lm / 2 」+1 1 ? i ? r - 1 ( ) ( ) 所以有 d X ′, Y ?2, d Y, X ′?2. 于是 x? y? x? xx? x? y? x 0 1 2 00 m - 20 0d iam m in因此 , 根据 D S的结构和对称性 , 可以得到 m ( )S = 2. m , n ( ) ( ) ( ) d X , Y ?2, d Y, X ?2. 综上所述 , d iam D S= 2m 引 理 4当 m , n ? 5 时 , 如 果 m< n ? 成立.m () ( ) - g m , 我们有d iamS= 2, 这里 m in m , n 设 F 是 { 0, 1,, m - 1 }的一个子集族 , 如果 F Lm / 2 」 () 中的任一集合都不被其他集合所包含 , 则称 F 为若 m ? 1 mod2 m () 若 m ? 2 mod4 0, 1, { , m - 1 }上的反链.() g m = m / 2 [ 6 ] ()若 m ? 0 mod4 引理 2设 F 是 [m ] ?= { 0, 1,, m - 1 }上的m / 2 + 1 m 证明 令 { Y , Y }是Y 的划分 , 这里 Y = { y , 一个反链 , 那么 F ?. 1 2 1 0 Lm / 2 」 , y} , Y= Y \ Y. 首先对 S[ V \ Y]中的边 y, m - 1 2 1 m , n 2 1 U ?U Α [ m ], | U | = 等号成立 , 当且仅当 F = 定向 , 使得到的有向图 D ′同构于 SD , 显然 , d iamm U ?U Α [m ], | U | = 「m / 2 . 1 Lm / 2 」或 () D ′= 2. 设 F 是 X 上的极大反链 , 由引理 2, 我们不引理 3 当 m , n ?5 时 , 如果n ?m , 则d iam m in 妨设F = U Α X ?| U | = Lm / 2 」 . 对 S中剩下的 m , n ( )= 2. S m , n + + ) ( 边如下定向 : 以任意的 y?Y, N y?F \ N i 2 i 证明 令 m = kn + r, k ?1, 0 ?r?n - 1. 令 { X, 1 + ++( ) () , N 〈x y,, N 〈x 〉, , N y〉 , 而且 X m - 1 0 X,m - 1 X 0, X, X ′}是 X 的一个划分 , 这里 X = { x, x, 2 k i i0 i1 + ( ) , x} 1 ?i?k , X ′= { z, z, , z}. 如果 n ( ) { N y?y?Y}是 X 上的一个反链. 由 n - m ? i, n - 1 0 1 r - 1 j j 2 = m , 由上文定义的 D S即为所求. 现在考虑 n < m m m +() - m - g m 以及 N 〈x 〉的性质可知该定X i Lm / 2 」(的情况. 首先对 S[ V \ X ′]中的边定向 这里 V = V m , n 向能够实现. 结合 D ′的定向 , 我们得到 S的定向 ( ) ) S, 得到的有向图 D ′满足 : m , n m , n ( ) D. 易见 , d Y, Y = 2. 对任意的x?X 和 y?Y, 我 ) 1 D ′[ X ?Y ]同构于 SD , 这里 1 ?i?k;i j 2 i n ) 们有 x?y或 y?x. 2 D ′[ X ?X ] \A 同构于 SD , 这里 1 ?i < j? i j j ii j j n ( ) k, A = { x, x?x, x?X , s?t}. + + j js jt js jt j ) ( 情形 1 x?y. 因为 N y- N 〈x〉?<, 所 i jj X i 113??第 2期王 培 :定向完全分裂图的最小有向直径 +++ + ++ ( ) ( ) ( )- N x ?N y 以 N y - N x ?<. 则有( ) () | = Lm / 2 」, 则 { N y ?y?Y }j X i k j X = F, 而且 |N y k k k ( )x使得 y?x?x. m - 1 m - 1 i j k i- = = ?( )N x Y i + + 1 Lm / 2 」-Lm / 2 」( ) 情形 2 y?x. 因为 N 〈x〉- N y?<, 所 j iX i j - + + + ( ) ( 由假设可知 , 对任意的 y?N x, 有 d x, k Y i i ( ) ( ) ( ) 以 N x - N y \ { x } ?<. 则有 x ?N x -X i j i k X i ( )+ - k + ) ( ) ( ) y= 2. 所以 , 存在 x?N x?N y. 令 F ′= k s X i k ) ( N y\ { x}使得 x?x?y. j i i k j+ ( ) ( ) { U ?F ?x?U 而且 X \U ?N x?< } , 于是 , ( ) ( ) 于是 , d X , Y?2, d Y, X ?2. 因此 d iami X i 2 2 m in- ) ( | F ′| ?|N ( )x|. 然而 , 由于 0 ?l?Lm / 2 」- 1, 则 = 2. S Yi m , n 3 m - 1 m - l - 1 m - 1 下面我们定义一个有向图 D S, 它的基础图是| F ′| = 1 - - ? 「m / 2 「m / 2 「m / 2 111m S, 这里 n = - m , 而且 m , n ?5. 令 { Y,m , n 1 m Lm / 2 」 , 因 此 , 如 果 n ?, 这 与 ?矛 盾 Lm / 2 」} , Y= { y,, yY}是 Y 的划分 , 设 Y= { y, y, m - 1 2 m 2 1 0 1 ( ) 3 则 d iamG?3. m in m , n , y} , D S 的定向满足 : X ?Y诱导的有向子图 n - 1 1 ( )接下来 , 给出 S的一个定向 D , 使得 d iam D m , n 同构于 D S, 而且m = 3. 令 { Y ′, Y ′}是 Y 的划分 , 其中 Y ′= { y, y, , + + 1 2 1 0 1 Α ) ( ) F \ N y, ,( { N y?y? Y} j j 2 0 m + + + y} , Y ′= Y \ Y ′, 这里 t = - m. 由于 m ?t - 1 2 1 ( ) N y, N 〈x〉, , N 〈x〉 Lm / 2 」m - 1 X0 Xm - 1 + ) ( ) 5, 则 t?m. 首先对 S (V \ Y ′中的边定向 , 使得到同时 { N y ?y ?Y }是 X 上的反链 , 这里 F 是 X 2 j j 2 m , n 3 ( ) m 的有向图 D ′同构于 D S , 显然 , d iam D ′= 2. 对 . 由于 m ?5, n - m =- 2m ?上的极大反链+ Lm / 2 」 S 中剩余的边定向如下 :对任意的 y ?Y ′, 令 N m , n j 2 3 () 0. 由引理 4可知 , d iam D S= 2. + ( ) ) ( y= N y. 易见 , 对任意的 x?X , y?Y ′, 有 d j 1 i j 2 m ( ) ) ( )( x, y?2 和 d y, x?2; 对任意的 y?Y ′i?1 引理 5 当 m , n ?5 时 , 如果 i j j i i 1 n ?, Lm / 2 」( ) ( ) 和 y?Y ′, 我们有 d y, y= d y, y= 2; 而且 , 对 j 2 i j j i ( ) d iamS= 3. m in m , n ( ) 任意的y , y ?Y ′?{ y } j?k , 有j k 2 0 m m , 需要证明 , 如果 n ?, 则证明 首先 y ? x? x ? yk j Lm / 2 」- 1 2 L」 Lm / 2 」 ( ) 所以 , d y, y?3. 综上所述 ,结论成立. j k m ( ) , 由引理 2 可d iamS?3. 如果 n > 显然 ,引理 3 —引理 5可以推出定理 1. m in m , n Lm / 2 」 + + ) ( 知 , 存在 2 个不同的点 y, y?Y, 使得 N yΑ N i j i : 参考文献 m ( ) ( ) 的情y, 因此 d y, y?3. 现在考虑 n = j i j [ 1 ] Chen Bo rliang, Fu H unglin. Edge dom ina tion in comp le te Lm / 2 」 ( ) p a rtite grap h [ J ]. D isc re te M a th, 1994 132: 29. () 况 , 假设存在一个 S的定向 D 使得 d iam D = 2. m , n [ 2 ] Fo lde s S, H amm e r P L. Sp lit grap h s [ C ] / /Hoffm an F. + 于是 , 对任意 2 个不同的点 y, y?Y, 我们有 N i j P roceed ings of the 8 th Sou th2Ea ste rn Confe rence on Com 2 + + ( ) ( ) ( ) y- N y?<, 那么由引理 2 可知 { N y?y i j i ib ina to ric s, Grap h Theo ry and Comp u ting. Lou isiana: B a ton + ( ) ?Y } = F, 而且我们不妨设 |N y | = Lm / 2 」. 由于i Rouge, 1977: 311 - 315. F 是 X 上的极大反链 , 所以存在 x?X 和 y?Y 使得 i j [ 3 ] Boe sch F, Tinde ll R. Robb in s’theo rem fo r m ixed m u lti2 + + + + ( ) )( ) ) ( ( grap h [ J ]. Am e r M a th Mon th ly, 1980 , 87: 716. N xΒ N y或者 N x< N y. X i j X i j + + [ 4 ] So lte s L. O ren ta tion s of grap h m inm izing the rad iu s o r the ( ) ( ) 情形 1 y?x. 因为 x?N y\N x, 所 j ii j X i ( ) d iam e te r[ J ]. M a th Slovaca, 1986 , 38 3 : 289. + + ( ) ( ) ( ) 以只能是 N x < N y , 则我们有 d x , y ?X i j i j [ 5 ] Gu tin G. m inm izing and M axim izing the d iam e te r in o ri2 3, 与假设矛盾.en ta tion s of grap h s[ J ]. Grap h s and Com b ina to ric s, 1994, + + ( ) ( ) 情形 2x?y. 如果 N xΒ N y, 则我们 i jX i j 10: 225. + ( )有 d y, x j i ( ) ? 3, 与 假 设 矛 盾. 所 以 N x< X i [ 6 ] Enge l Kon rad. Sp e rne r Theo ry [ M ]. Cam b ridge: Cam 2 + + ( ) ( ) N y, 令 l = |N x| , 则 0 ?l?Lm / 2 」- 1. 因为 b ridge U n ive rsity P re ss, 19 97. j X i