P_m_S_n的点可区别全色数
Pm ?Sn 的点可区别全色数
安明强 ( )天津科技大学 理学院 , 天津 300457
( ) ( ) ( ) ( ) ( ) 摘要 :设 G 是简单图 , f 是从 V G?E G到{ 1 , 2 ,, k} 的一个映射. 对每个 u ?V G, 令 C u= { f u} ?
( ) ( ) ( ) ( ) ( ) ( ) { f uv| v ?V G, u v ?EG} . 如果 f 是 k2正常全染色 , 且对任意 u , v ?V G, 有 Cu?Cv, 那么称 f 为图 G 的
( ) ( ) χ点可区别全染色 简称为 k2VD TC. 数G= min{ k| G 有 k2VD TC} 称为图 G 的点可区别全色数. 给出 m 阶路v t P 和 n + 1 阶星 S 的联图的点可区别全色数.m n
关键词 : 全染色 ; 点可区别全染色 ; 点可区别全色数
中图分类号 : O157 . 5文献标识码 : A
Vertex2dist inguishing total2chromat ic number of P?Sm n
A N Mi ng2qia ng
( )College of Science , Tia nji n U niver sit y of Science & Technolo gy , Tia nji n 300457 , Chi na
) ( ) ( ( )= Abstract : L et G be a si mp le grap h a nd f be a mappi ng f ro m V G?E Gto { 1 ,2 , , k} . L et C u ( ) ( ) ( ) ( ) ( ) f wa s a k2p rop e r to t al2colo ri ng a nd If { f u} ?{ f u v | v ?V G, u v ?E G}u ?V G.fo r eve r y
( ) ( ) ( ) Cu?C vfo r eve r y u , v ?V G, t he nk2ver t e x2di sti ngui shi ng to t al2colo ri ng of f wo ul d be called a s
χ( ) ( ) Gk2VD TC of G fo r sho r t . The n umber G= mi n{ k| G ha d a k2VD TC} wo ul d be called a s ver t e x2di s2v t ti ngui shi ng to t al2c hro matic numbe r . The ver t e x2di sti ngui shi ng to t al2c hro matic numbe r o n t he joi n grap h of
( ) m2o r der p at h Pa nd n + 12o r der st a r S wa s give n . m n
Key words : to t al2colo ri ng ; ver t e x2di sti ngui shi ng to t al2colo ri ng ; ve r t e x di sti ngui shi ng to t al2ch ro matic numbe r
称为 是 G 的 一 个k2点 可 区 别 全 染 色 , 简 记 为 本文所考虑的图均为连通的 、有限的、无向的简
单图. 文[ 1,3 ]对点可区别边染色问题进行讨论. 张 k2VD TC. 称[ 4 ] 忠辅等讨论图的邻点可区别边染色问题. 现在有 mi n{ k | G 存在 k2VD TC} = χ( ) Gv t [ 5 ] [ 6 ] 很多国外学者对此进行研究. 张忠辅等进一步 为 G 的点可区别全色数.提出邻点可区别全染色的概念 ,讨论圈 ,完全图 ,完 ( ) ( ) 令 nG
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示 G 的 d 度顶点个数 , 令 k G=d T 全二部图 ,扇 ,轮 ,树的邻点可区别全色数. 但点可区
l 别的全染色 ,比邻点可区别的全染色研究难度大 ,现 ( ) δ Δ mi n{ l| ?nG , ?d ? } .d [ 7 ,8 ] 在得到的结果较少. d + 1
[ 8 ]( ) 猜想 1对简单图 G , | V G| ?2 , 有
[ 8 ]( ) ( ) ( ) χ k G?G?k G+ 1T v t T 定义 1设 G 是阶数至少为 2 的连通简单[ 7 ,8 ] 引理 1当 n ?3 时 ,( ) ( ) , k} 图 , k 是正整数 , f 是从 V G?E G到{ 1 , 2 ,
( ) n + 1 , n ?0 mo d 2( ) ( ) ( ) ( ) 的一个映射 , 使 Π u v ?E G, f u?f v, f u? ( ) χ ( ) χ K= K= n n at v t ( )n + 2 , n ?1 mo d 2 ( ) ( ) ( ) ( ) ( ) f u v? f v; Π u v , u w ?E Gv ? w , f u v? [ 9 ] 定义 2设 G 和 H 是两个边不相交的简单( ) ( ) ( ) ( ) ( ) f u w ; Π u , v ?V G, C u?C v, 或 : C u? ( ) ( ) ( ) ( ) ( ) 图 , V G ?H= V G?V H, E G ?H= E G?( ) ( ) ( ) ( ) ( ) v, 其中 C u= { f u} ?{ f u v| v ?V G,C ( ) ( ) ( ) E H?{ u v| u ?V G, v ?V H} , 则称 G ?H 为( ) ( ) ( ) 2C u , 则 f , k } u v ?E G} , C u = { 1 , 2 , G 和 H 的联图.
β文[ 7 ]对一些特殊图的距离不超过的点可区 收稿日期 : 2007 206 215
( ) 作者简介 : 安明强1982 2, 男 , 甘肃天水人 , 硕士 , 讲师.别全色数进行研究. 本文研究更复杂情形 , 讨论 m
兰 州 理 工大 学 学 报 ?164 ?第 34 卷
) 阶路 P 和 n + 1 阶星 S 的联图的点可区别全染证明 1当 m = n = 2 时 , P?S = P?P, 由m n m n 2 3
) 色 ,并给出其点可区别的全色数. 文中未加述及的术 定理 1 中的 2知结论为真.
) 语和符号可参见文[ 9 ] . 2 当 m = 3 , n = 2 时 , Pm ?S n = P3 ?P3 , 由于
( ) ) ( P= vv = { u, u, , k P?P= 7 , 所以以下设m 1 2vm , V S n 0 1 T 3 3
χ ( ) ( ) u} , E S = { uu| i = 1 , 2 , P?S ?7n n 0 i , n} . 3 2 v t
定理 1 对 m ? n = 1 , 有令 f 为
) ) ) ( ( ( f uv= i , f uv= i + 1 , f uv= i + 2 , 1 , 2 1 i 2 i 3 i m = 5
χ ( ) ( ) ( ) ( ) i = 1 , 2 , 3, f uu = i + 5 i = 1 , 2; m = 3 Pm ?S 1 = 6i i + 1 v t
( ) ( ) ( ) f vv = i + 4 , i = 1 , 2, f u= i + 3 , m ?4m + 3 i i + 1 i
) ( ) ( ) ( ) ( ) i = 1 , 2 , 3, f v= 7 , f v= 1 , f v= 2 . 证明 1当 m = n = 1 时 , 或 m = 2 , n = 1 时 ,1 2 3
易知 f 为 P?S的 72VD TC 法. P?S= K或 P?S= K, 由引理 1 知结论为3 2 1 1 3 2 14
) ( ) ( ) χ 3当 m ?4 , n = 2 时 ,χ 真 , 即K=K4 = 5 .3 v t v t
) P3 ?S1 = P3 ?P2 , 由l 2当 m = 3 , n = 1 时 , 即( ) Pk ?S = mi n T m?2 ,2 l ( )( )χ 4 + 1 于 k P?P= 6 , 所以P?S?6 . 若要证T 3 2 3 1 v t
l 明结论成立 ,仅需给出它的一个 62VD TC 法. 令 2 , ?m -( ) ( ) ( ) f : f uv= i , i = 1 , 2 , 3, f uv= i + 1 , 5 + 1 1 i 2 i
( ) ( ) l i = 1 , 2 , 3. f uu= 5 ;1 2 ?2 ,( )( ) ( ) ( )( )m + 1 = + 1 f vi v i + 1 = i + 4 , i = 1 , 2, f u1 , f u2 = 6 ) ) ( ( 1 , f v= i + 2 , i = 1 , 2 , 3.l i ?1 = m + 3 ( )+ 1 m + 2 易知 f 是 P?S 的 62VD TC 法.3 1
) 因此 ,3当 m ?4 时 ,
χ ) l ( ?S2 ?m + 3Pm v t ( ) mi n l = k P?S?2 ,T m 1 令 f 为3 + 1
( ) ( ) ( )l f uv= i , f uv= i + 1 , f uv= i + 2 , 1 i 2 i 3 i 2 , ?m -) ( , m; i = 1 , 2 , 4 + 1
( ) ( ) ( ) f vv= i + 3 , i = 2 , 3 , , m, f uu= i - 1 i l 1 2 = m + 3 ?2( ) ( ) m + 1+ 1 m + 3 , f uu= 1 ;2 3
( ) ( ) ( ) ( χ ( ) 因此 ,P?S?m + 3 . 若要证明结论成立 , 仅f ui = m + i , i = 1 , 2 , 3, f vi = i - 1 , i = 2 ,m 1 v t
) ( ) ( , m, f v= 4 .) 需给出它的一个 m + 32VD TC 法. 令3 , 1
) )对以上的 f 有( ( f : f uv= i , f uv = i + 1 , i = 1 , 2 , 1 i 2 i , m ;
( ) ( ) { m - 1 , m , = ? C v= { 1 , 2 , 3 , 4 , 5} , C v ) ( 1 m f vv = i + 3 , i = 1 , 2 ,, m - 1 ; i i + 1
m + 1 , m + 2 , m + 3} ; ) ) ) ( ( ( f uu= m + 3 , f u= m + 1 , f u= m + 2 ; 1 2 1 2
) ) ( ( ) ) ( ( ? C v= { 1 , 2 , 3 , 4 , 5 , 6} , C v一定缺 i - 2 2 i f vi = i - 1 , i = 2 , 3 ,, m ; f v1 = m + 3 .
色 , i = 3 , 4 ,, m ; 对以上的 f 有
) ) ( ( ( ) ( ) ? C u缺 m + 2 色 , C u缺 2 色. C v= { 1 , 2 , 3 , 4 , 5 } , C v一定缺 i -2 1 3 ? 2 i
( ) 故 f 是 P ?S 的 m + 32VD TC 法. , m - 2 ; m 2 综上知 ,色 , i = 3 , 4 ,
定理结论为真.( ) ( ) ? C u缺 m + 2 色 , C u缺 1 色 ;1 2
定理 3 对 m ?n = 3 , 有) ) ( ( ? C v= { 1 , 2 , 4 , m + 3} , C v = { m - 1 , m , 1 m
8 m = n = 3 m + 1 , m + 2} . χ ( ) P?S =m n v t ( ) m + 4 m > 3 , n = 3 故 f 是 P m ?S 1 的 m + 32VD TC 法.综上知 ,
) ( ) 证明1当 m = n = 3 时 , 由于 k P?S= 定理结论为真.T 3 3
8 , 所以定理 2 对 m ? n = 2 , 有
χ ( ) P3 ?S 3 ?86 m = n = 2 v t
χ 令 f 为( ) = 7 m = 3 , n = 2 P?S m n v t
( ) ( ) ( ) f uv= i , f uv= i + 1 , f uv= i + 2 ,m ?4 , n = 21 i 2 i 3 i m + 3
第 5 期安明强 : P?S 的点可区别全色数?165 ?m n
( ) ( ) i = 1 , 2 , 3, f v= 7 ; m - 1 . 1
( ) ) ( ) ( ( ) f uu= i - 1 , i = 2 , 3, f uu= 7 , 当 m ?0 mo d 2时 ,0 i 0 1
) ) ( ) ( ( f uv= i + 3 , i = 1 , 2 , 3, f v= 1 ;( ) ( ) 0 i 2 ? C v= { 1 , 2 , 3 , 4 , 6 , m + 3} , C v= { 1 , 2 , 1 m
( ) ) ( ) ( ) ( f vv= i + 4 , i = 2 , 3, f u= 8 , f u=i - 1 i 0 1 m , m + 1 , m + 3 , m + 4} . ( ) ( ) ) ( f u= f u= 6 , f v= 2 .( ) ( ) 2 3 3 ? C u= { m + 1 , m + 2 } , C u= { m + 2 ,1 2
易知 f 是 P?S 的 82VD TC 法.3 3 ( ) m + 3} , C u= { m + 2 , m + 4} . 3
) 2当 m > 3 , n = 3 时 , 由于 ( ) ( ) ? C v= { 2 , 3 , 5 , 6 , 7 , m + 3 , m + 4} , C v一2 i
l - 1 . , m 定缺 i - 1 色 , i = 3 , 4 ,( ) k P?Smi n l = ?2 ,T m3 5 + 1 ( ) 故 f 是 P m ?S 3 的 m + 42VD TC 法.
l 综上知 ,定理结论为真.2 , ?m -6 + 1 定理 4 当 m ? n ?4 时 , 有
l χ ) ( P?S = m + n + 1m n v t ?3 ,( )m + 1+ 1 证明 由于
l l = m + 4 ?1( ) k P?S = mi n?m ,T m n l + 1 ( )m + 3 ( ) m + 1+ 1
所以l ?2 ,χ ( ) P?S? m + 4( )m 3 m + 2 + 1 v t
令 f 为l ?m - 2 ,( ) ( ) ( ) f uv= i + 3 , i = 1 , 2 ,, m, f uu= m + 0 i 0 1 ( )m + 3 + 1
) ) ( ( 4 , f uu= 1 , f uv = 1 ;0 2 3 m l ?1 = m + n + 1( ) ( ) ( ) ( f u0 = 3 , f u0 u3 = 2 , f vi v i + 1 = i + 5 , i = ( )+ 1 m + n
) ( ) 1 , 2 , , m - 1, f uv= i ;1 i 所以
( ) ( f uv= i + 1 , i = 1 , 2 , ) ( )= i + 2 i , m; f uvχ ( ) 3 i Pm?S n ?m + n + 1v t
( ) 2 , i = 1 , 3 , 4 , , m - 1. ) 1当 m = n ?4 时 , 令 f 为
( ) 当 m ?1 mo d 2时 ,( ) ( ) ( ) u1 v j = j , j = 1 , 2 ,, m, f u2 v j = j + 1 ,f
) ) ) ( ) ( ( ( f u= f u= f u= m + 3 , f v=1 2 3 1 ) ( j = 1 , 2 , , m;
( ) f v = m + 2 ;m 对 uv 用 i , i + 1 ,, m + 1 , 1 , 2 , , i - 2 循环i j
( ) ( ) ( f v= f v= i - 1 , i = 2 , 3 , 5 , 6 , i m - i + 1 , ( ) , m. n ; j = 1 , 2 , , 去染 , i = 3 , 4 ,
( ) ) m + 1/ 2 - 1; ( ) ( ) ( ) = n + i , i = 3 , 4 , f u0 = n , fu, n,i
( ) ( ) ( ) v = m + 4 , f v4 = f vm - 3 = 1 , f ( ) ( ) ( ) ( ) f u= f u= n + 2 , f v= 2 n + 1 ; m + 1/ 2 1 2 1 ( ) f uv= m + 2 .3 2 ( ) ) ( ) ( f v= i - 1 , i = 2 , 3 , , m , f vv = i i i + 1
( ) 当 m ?0 mo d 2时 ,( ) m + i + 2 , i = 1 , 2 , , m - 1.
( ) ( ) ( ) f u= f u= m + 2 , f u= 4 , 1 2 3 ( ) 易知 f 是 P m ?S n 的 2 n + 12VD TC 法.
( ) ( ) f v= m + 3 , f v= m + 4 , 1 2 ) ( 2当 m = n + 1 时 , uv 的染法同上 , i = 1 , 2 ,i j
( ) 1 i ?1 mo d 2) ; , m, n ; j = 1 , 2 ,
( )) ( i ?0 mo d 2f v= 2i ) ( )( , f uu, n( )= = i - 1 , i = 2 , 3 , 0 1 f uu0 i
( )= 3 , 4 , i , m ) ( ( ) 2 n + 2 , f uv= n + i , i = 1 , 2 , , m; 0 i
( )f uv3 2 = m + 3 ) ) ( ( ( ) f u0 = n , f ui = n + 1 + i , i = 3 , 4 , , n,
对以上的 f 有) ) ( ( f u= f u= n + 3 ;1 2
( ) 当 m ?1 mo d 2时 ,( ) ( ) ( f v= 2 n + 2 , f v= i - 1 , i = 2 , 3 , - , m 1 i
( ) ( )? C v= { 1 , 2 , 3 , 4 , 6 , m + 2 } , C v= { 1 , 1 m ) ( ) 1, f v = 2 n ;m
m , m + 1 , m + 2 , m + 3 , m + 4} . ( ) ( )= n + i + 2 , i = 2 , 3 , , m - 2 , f vv i i + 1
) ) ( ( ? C u= { m + 1 , m + 2 } , C u= { m + 2 , 1 2 ) ) ( ( f v1 v2 = 2 n + 1 , f v m - 1 v m = n + 3 .
( ) ( ) m + 4} , C u= { 4 , m + 4} . 易知 f 是 P ?S 的 2 n + 22VD TC 法.3 m n
( ) ( ) ( ) ( )?Π v, v , i ? j , C v?C v , i = 2 , 3 ,当 m = n + 2 时 , uv 的染法同上 , i = 1 , 2 ,3 i j i j i j ,
兰 州 理 工大学学报 ?166 ?第 34 卷
) , m; m = 2 , n = 3 7 , n ; j = 1 , 2 ,
m = 2 , n ?4 ( ) ( ) ( ) n + 4 f u0 ui = i - 1 , i = 2 , 3 ,, f u0 u1 = m +, nm = 3 , n ?4 n + 5 ) ( ( ) n + 1 , f uv= n + i , i = 1 , 2 ,, m; 0 i n ? m ?4m + n + 1 ( ) ( ) - 2, , m f vi v i + 1 = n + 2 + i , i = 1 , 2 ,
) 证明 1当 m = 2 , n = 3 时 , 由于( ) ) ( f v v= n , f u= n ;m - 1 m 0
( ) k P?S= 7T 2 3 ) ) ) ( ( ) ( ( f ui = m + i , i = 3 , 4 ,, n, f u1 = f u2 =
所以( ) ( ) n + 4 ; f v1 = n + 2 , f v2 = 2 n + 3 ;
χ ( ) P2 ?S 3 ?7) ( ( ) v t , m - 1, f vi = i - 2 , i = 3 , 4 ,
令 f 为( ) f v = 2 n + 3 .m
) ) ) ( ) ( ( ( f u= 3 , f u= 6 , i = 1 , 2 , 3, f v= 7 , 0 i 1 ( ) f 是 P m ?S n 的 2 n + 32VD TC 法.显然
( ) ( ) f v= 1 , f vv= 6 ;2 1 2 ) 4当 m > n + 2 时 , 由于
( ) ( ) ( ) ( f uv= i , i = 1 , 2, f uv= i + 1 , i = 1 ,1 i 2 i l ( ) k P?S mi n l = ?2 ,T m n ) ( ) ( ) 2, f uv= i + 2 , i = 1 , 2;3 i ( ) n + 2+ 1
( ) ) ( ) ( f uu= i - 1 , i = 2 , 3, f uu= 7 , 0 i 0 1 l ?m -2 , ( ) ( ) f uv= i + 3 , i = 1 , 2.0 i ( )n + 3 + 1 易知 f 是 P?S的 72VD TC 法. 2 3 l ?n , ) 2当 m = 2 , n ?4 时 , 由于( ) m + 1+ 1 l l ( ) k P?S = mi n l?n ,T 2 n ?1 = m + n + 13 + 1 + 1 ( )m + n
l 所以 ?3 = n + 4( ) n + 2+ 1 χ ( ) Pm ?S n ?m + n + 1v t 所以( ui v j 的染法同上 , i = 1 , 2 ,, n ; j = 1 , 2 , , χ ( ) P2 ?S n ? n + 4v t ) m. 令 f 为) ) ( ( ) ( u= i - 1 , i = 2 , 3 , , n, f uv= n + f u0 i 0 i ) ) ( , n ; j = 1 , 2 , ( f uv = i + j - 1 , i = 1 , 2 ,i j ) ( , m; i , i = 1 , 2 , ) ( ) ( f uu= i + 2 , i = 1 , 2 , , n;0 i ) ) ( ( ( f uu= m + n + 1 , f vv = n + 2 + i , i = 0 1 i i + 1 ( ) ( ) ( ) f v1 v2 = n + 4 , f u0 v1 = n + 3 , f u0 v2 = 1 ,) ( ) 1 , 2 , , m - 1, f u= n ;0 ( ) f u= 2 ;0 ) ( ( ) ( ) ) ( f u= m + i , i = 3 , 4 , = f u= , n, f ui 1 2 ) ( ( ) ) ( f u= n + 3 , i = 1 , 2 , , n, f v= n + i , i i m + 2 ; ( ) i = 1 , 2. ( ) ( ) ( ) ( f v1 = f v n + 1 = m + n + 1 , f vi = i - 1 , i =( ) 的 n + 4 2VD TC 法. 易知 f 是 P?S2 n 2 , 3 , , n , n + 2 , ) , m. ) 3当 m = 3 , n ?4 时 , 由于 对以上的 f 有l ( ) mi n l = k P?S ?n , T 3 n ( ) ? C v= { 1 , 2 ,, n , n + 1 , n + 3 , m + n + 1} , 1 4 + 1 ) ( Cv= { 1 , 2 , - 2 , m - 1 , m , m + 1 , m + n , m + , n m l ?2 ,n + 1} . ( )n + 2 + 1 ( ) ( ) ( ) ? n + 2 + i ?C vi 2C vi - 1 ?C v? ?i - 2 l ?2 = n + 5( ) ( ) Cv, i = 3 , 4 , , m - 1. i - m + 3 ( )+ 1 n + 3
( ) = { 1 , 2 , ? C u, m - 2 , m - 1 , m , m + 2 , 1 所以
( )( ) ( ) m + n + 1} , m + i ?C ui - C ui - 1 ?C ui - 2 ?χ ( ) P?S ?n + 53 n v t ( ) ( ?C u, i = 3 , 4 ,i - n + 2 ) , n. 令 f 为
( ) 故 f 是 P m ?S n 的 m + n + 12VD TC 法.综上( ) ( ) 1 i = 1 , 2 , , n ; j = 1 , 2 , 3, f uv = i + j -i j
知 ,定理结论为真.( ) ( ) ( ) f v1 = n + 5 , f vi = i - 1 i = 2 , 3;
定理 5 当 n ? m ?2 时 ,有( ) ( ) ( ) f uu= i - 1 i = 2 , 3 , , f uu= n + , n0 i 0 1 χ ( ) P?S =m n ( ) ( ) v t 5 , f uv= n + i i = 1 , 2 , 3;0 i
第 5 期安明强 : P?S 的点可区别全色数?167 ?m n
) ) ) )) ( ( ( ( ( . , mf vv= n + 4 , f vv= n + 5 , f u = i - 1 i = 2 , 3 , f v= n , 1 2 2 3 0 i
( ) ) ( ( ) 易知 f 是 P m ?S n 的 m + n + 12VD TC 法.f ui = n + 2 i = 1 , 2 ,, n.
( ) 综上知 ,定理结论为真.显然 f 是 P3 ?S n 的 n + 52VD TC 法.
) 4n ?m ?4 . 参考文献 : 当 n = m ?4 时 , 定理 4 已证.
[ 1 ] BAL IS T ER P N ,BOLL OBA S B , SC H EL P R H . Ver t ex di s2 当 n > m ?4 时 , 由于Δ( ) ti ngui shi ng colo ri ngs of grap hs wit h G= 2 [ J ] . Di scret e l Mat he matics ,2002 ,252 : 17229 . ) ( ?S = mi n ?2 ,k Pn l T m ( )+ 1 n + 2 BAL IS T ER P N , R IO RDA N O M , SC H EL P R H . Ver t ex di s2 [ 2 ]
l ti ngui shi ng edge colo ri ngs of grap h s [ J ] . J of Grap h Theo r y , 2 , ?m -( ) 2003 ,42 2: 952109 . ( )n + 3 + 1
BU R R IS A C , SC H EL P R H . Vert ex2di sti ngui shi ng p rop er [ 3 ] l ( ) ?n ,edge2colo ri ngs [J ] . J of Grap h Theo r y ,1997 ,26 2:73282 . ( ) m + 1+ 1 Z HA N G Zho ngf u , L IU Li nzho ng , WA N G J ia nf a ng . Adjacent [ 4 ] l st ro ng edge colo ri ng of grap hs [ J ] . Applied Mat he matics L et2 m + n + 1 ?1= ( )m + n + 1 t er s ,2002 ,15 :6232626 .
ΔHA TA M I H .+ 300 i s a bo und o n t he adjacent vert ex di sti n2 所以[ 5 ]
gui shi ng edge chro matic nu mber [J ] . J of Co mbi nato rial Theo2 χ ( ) P?S ? m + n + 1m n v t r y , Ser B ,2005 ,95 :2462256 . 令 f 为ZHA N G Zho ngf u , C H EN Xia ng’en ,L I J i ngwen , et al . On t he [ 6 ] ) ( ) ( ( ) ( f uv= n + i i = 1 , 2 ,, m, f ui v 1 = i i =0 i adjacent vert ex di sti ngui shi ng to t al colo ri ng of grap hs [J ] . Sci2
( ) ence i n Chi na , Ser A ,2004 ,34 5: 5742583 . ) ; , n1 , 2 ,
β 张忠辅 ,李敬文 ,陈祥恩 ,等. 图的距离不大于的点可区别的( ) ( ) ( ) f uv = i + 1 i = 1 , 2 ,, n, f v= m + n + i 2 1 [ 7 ] ( ) 全染色 [J ] . 中国科学 : A 辑 ,2006 ,36 10: 1 11921 130 . 1 ; ZHA N G Zho ngf u , C H EN Xia ng’en ,L I J i ngwen , et al . Vert ex [ 8 ] ui v j 用 j , j + 1 ,, n + 1 , 1 , 2 , , j - 2 循环去di sti ngui shi ng to t al colo ri ng of grap h s [ J ] . A r s Co mbi nato ria ,
2008 ,87 :33245 . ( ) 染 , j = 3 , 4 ,, m.
BOND Y J A , MU R T Y U S R. Grap h t heo r y wit h applicatio n s ( ) ( )( = i - 1 i = 2 , 3 , f vi - 1 vi = n + i + 1 , f u0 ui [ 9 ] [ M ] . Lo ndo n : Macmilla n Press L t d ,1976 . ) ) ( , m, f uu= m + n + 1 ;0 1
) ) ( ( ( ) m , , f u= n , f = n + 2 i = 1 , 2 , u0 i
浙公网安备 33021202002483