若干笛卡尔积图的点可区别全色数

收稿日期:2008203220.基金项目:连云港师专科研课题资助项目(L SZTD200806);连云港师范高等专科学校青蓝工程资助项目.作者简介:王继顺(19702),男,山东临沭人,连云港师范高等专科学校讲师,硕士,主要从事图论与组合优化,计算机辅助几何设计研究. 文章编号:16722691X (2009)0120003203C m ×K n 的邻点可区别全染色王继顺1,李步军2(1.连云港师范高等专科学校数学系,江苏连云港222006;2.淮海工学院数理科学系,江苏连云港222005)摘　要:设G (V ,E )是阶数至少为2的简单连通图,k 是正整数,V ∪E 到{1,2,3,…,k}的映射f 满足:对任意uv ,vw ∈E (G ),u ≠w ,有f (uv )≠f (vw );对任意uv ∈E (G ),有f (u )≠f (v ),f (u )≠f (uv ),f (v )≠f (uv );那么称f 为G 的k 2正常全染色,若f 还满足对任意uv ∈E (G ),有C (u )≠C (v ),其中C (u )={f (u )}∪{f (uv )|uv ∈E (G ),v ∈V (G )},那么称f 为G 的k 2邻点可区别的全染色(简记为k 2AVD TC ),称min {k |G 有k 2邻点可区别的全染色}为G 的邻点可区别的全色数,记作 at (G ).本文得到了圈C m 和完全图K n 的笛卡尔积图C m ×K n 邻点可区别的全色数.关键词:图;全染色;邻点可区别全染色;邻点可区别全色数中图分类号:O157.5 文献标识码:A　引言具有重要的实际意义和理论意义的图的染色问题,是图论研究的主要内容之一.文[1]提出图的邻点可区别全染色的概念,得到了圈、完全图、扇、轮、树等特殊图的邻点可区别全色数,并给出了相应的猜想.为验证这一猜想,文[2～5]研究了一些特殊图及由图的不同运算所得到的图的邻点可区别的全染色问题.图的染色的基本问题就是确定其各种染色法的色数,该类问题属于N P 难问题.笛卡儿积图是图论中重要的一种图,也是在计算机信息网络、交通网络等实际中常见的一种图,具有重要的研究意义和广泛的应用价值.文[5]研究了路P m 与完全图K n 笛卡尔积图P m ×K n 的邻点可区别的全染色问题,得到了该笛卡尔积图的邻点可区别的全染色数.本文研究了圈C m 与完全图K n 的笛卡尔积图C m ×K n 的邻点可区别的全染色,得到其邻点可区别的全染色数,说明文[1]的猜想是正确的.定义1[1]　设G (V ,E )是阶数至少为2的简单连通图,V ∪E 到{1,2,3,…,k}的映射f 满足:(1)对任意u ,v ,w ∈V (G ),uv ,vw ∈E (G ),u≠w ,有f (uv )≠f (vw );(2)对任意u ,v ∈V (G ),uv ∈E (G ),有f (u )≠f (v ),f (u )≠f (uv ),f (v )≠f (uv );那么称f 为G (V ,E )的k 2正常全染色.若f 还满足(3)对任意uv ∈E (G ),有C (u )≠C (v ),其中C (u )={f (u )}∪{f (uv )|uv ∈E (G ),v ∈V (G )}.那么称f 为G 的k 2邻点可区别的全染色(简记为k 2AVD TC ),称min {k |G (V ,E )CSP k 2AVD TC }为G (V ,E )的邻点可区别的全色数,记作 at G (V ,E ).猜想[1]　对阶数不小于2的简单连通图G(V ,E ),有 at (G )≤△(G )+3.其中△(G )为G (V ,E )中顶点的最大度.令珚C (u )={1,2,…,k}-C (u ),如果对任意u ,v ∈V (G ),uv ∈E (G ),C (u )≠C (v ),则珚C (u )≠珚C (v ),反之也成立.定义2[1]　令C m 为圈,K n 为完全图,并设V (C m )={u 1,u 2,…,u m },E (C m )={u 1u 2,u 2u 3,…,u m-1u m ,u m u 1};V (K n )={v 1,v 2,…,v m },E (K n )={v i v j |i ,j =1,2,….n ,i <j}.构造C m 与K n 的笛卡尔积图如下:第23卷第1期甘肃联合大学学报(自然科学版)Vol.23No.1　2009年1月Journal of G ansu Lianhe University (Natural Sciences )Jan.2009　V (C m ×K n )={w ij |i =1,2,…,m ;j =1,2,…,n},E (C m ×K n )={w ij w st |i =s且v j v t ∈E (K n )或者j =t 且∈v i v s ∈E (C n )}.所构造的笛卡尔积图以下简记作C m ×K n .文中所考虑的是有限无向简单连通图,用到的未加说明的术语或记号可参见文献[6～8].　主要结果引理1[1]对阶数不小于2的简单连通图G(V ,E ),若G 有两个相邻的最大度顶点,则at (G )≥△(G )+2;如果G 最大度点都不相邻,则有at (G )≥△(G )+1. 引理2[1]设有m 阶圈C m (m ≥4),则at (C m )=4, 对于n 阶完全图K n (n ≥3),有at (K n )=n +1,n ≡0(mod2),n +2,n ≡1(mod2). 由于当n =1时,易见C m ×K 1=C m ,由引理1,可得如下结论成立.定理1　m 阶圈C m (m ≥4)与n 阶完全图K n的笛卡尔积图为C m ×K n ,则当n =1时,at (C m ×K n )=4,m ≥4. 定理2　m 阶圈C m (m ≥4)与n 阶完全图K n 的笛卡尔积图为C m ×K n ,则当n ≥2时,at (C m ×K n )=n +3,m ≥4. 证明　由引理1可得, at (C m ×K n )≥n +3.为证明 at (C m ×K n )=n +3,只需证明C m ×K n 存在一个(n +3)2AVD TC ,现分两种情况证明如下.情形1　当m ≡0(mod2)时,设由n +3种颜色组成的色集合为C ={1,2,…,n +3},对图的边或顶点染色确定为c ,为保证c ∈C ,若c 比1小或者大于n +3,c 的取值为r ,这里r ∈{1,2,…,n +3}且c ≡r (mod n +3).现构造V (C m ×K n )∪E(C m ×K n )到C 的映射f 如下:f (w ki w kj )≡i +j -2,i =1,2,…,m ,j =1,2,…,n.当1≤k ≤m -1时,分别有f (w kj )≡n +j -1,k ≡1(mod2),f (w kj )≡n +j ,k ≡0(mod2),j =1,2,…,n;当k =m 时,f (w mj )≡n +j +1(mod n +3),,j =1,2,…,n;当j =1时,分别有f (w k 1w k+11)=n +3,1≤k ≤m -2,且k ≡1(mod2),f (w k 1w k+11)=n +2,1≤k ≤m -2,且k ≡1(mod2),其中若k =m -1,令f (w m-11w m 1)=n +3.当2≤j ≤n 时,分别有f (w kj w k+1j )≡2(j -1),1≤k ≤m -1,且k ≡1(mod2),f (w kj w k+1j )≡n +j +1,1≤k ≤m -1,且k ≡0(mod2),而f (w mj w 1j )≡n +j ,j =1,2,…,n;按照如上的染色法,可得当k =1时珚C (w kj )=n +j -1(mod n +3),j =1,2,…,n;当2≤k ≤m 时,分别有珚C (w kj )=n +j +1(mod n +3),k ≡0(mod2),珚C (w kj )=n +j (mod n +3),k ≡1(mod2),j =1,2…,n. 为此,图中任意相邻的顶点都有不同的邻点可区别的染色集合.所以f 是笛卡尔积图C m ×K n 的(n +3)2AVD TC .情形2　当m ≡1(mod2)时,设由n +3种颜色组成的色集合为C ={1,2,…,n +3},对图的边或顶点染色确定为c ,为保证c ∈C ,若c 比1小或者大于n +3,c 的取值为r ,这里r ∈{1,2,…,n +3}且c ≡r (mod n +3).现构造V (C m ×K n )∪E (C m ×K n )到C 的映射f 如下:f (w ki w kj )≡i +j -2,i =1,2,…,m ,j =1,2,…,n.当1≤k ≤m -1时,分别有f (w kj )≡n +j -1,k ≡1(mod2),j =1,2,…,n ,f (w kj )≡n +j ,k ≡0(mod2),j =1,2,…,n.当k =m 时f (w mj )≡n +j +1,j =1,2,…,n;当j =1时,分别有f (w k 1w k+11)=n +3,1≤k ≤m -2,且k ≡1(mod2),f (w k 1w k+11)=n +2,1≤k ≤m -2,且k ≡0(mod2),4 甘肃联合大学学报(自然科学版) 第23卷其中若k =m -1,令f (w m-11w m 1)=n ,当2≤j ≤n 时,分别有f (w kj w k+1j )≡2(j -1),1≤k ≤m -2,且k ≡1(mod2),f (w kj w k+1j )≡n +j +1,1≤k ≤m -2,且k ≡0(mod2),其中若k =m -1,f (w m-1j w mj )=n +j -1,j =2,…,n ,而f (w mj w 1j )≡n +j ,j =1,2,…,n;由如上的染色法,可得当k =1时,珚C (w kj )=n +j +1(mod n +3),j =1,2,…,n;当2≤k ≤m 时,分别有珚C (w kj )=n +j +1(mod n +3),k ≡0(mod2),珚C (w kj )=n +j (mod n +3),k ≡1(mod2),j =1,2…,n.当k =m -1,m 时珚C (w m-1j )=n +j +1(mod n +3),j =1,2,…,n ,珚C (w mj )=2(j -1)(mod n +3),2≤j ≤n ,而珚C (w m 1)=n +3.容易验证对V (C m ×K n )中任意相邻两顶点的染色集合不同,所以C m ×K n 存在(n +3)2AVD TC .综上可得,结论成立.参考文献:[1]张忠辅,陈祥恩,李敬文,等.关于图的邻点可区别全染色[J ].中国科学(A 辑),2004,34(5):5742583.[2]王治文,王莲花,王继顺,等.关于θ2图的邻点可区别的全染色[J ].兰州交通大学学报:自然科学版,2004,23(3):13215.[3]王继顺,邱泽阳,张忠辅,等.联图F n ∨P m 的邻点可区别全染色[J ].应用数学学报,2006,29(5):8792884.[4]L I Jing 2wen ,YAO Bing ,CH EN G Hui ,et al.Adjacentvertex 2distinguishing edge chromatic number of C n ×K n [J ].Journal of Lanzhou University :Natural Sci 2ences ,2005,41(1):96298.[5]CH EN Xiang 2en ,ZHAN G Zhong 2f u.Adjacent 2Ver 2tex 2Destinguishing Total Chromatic Number of P m ×K n [J ].Journal of Mathematical Research and Expo 2sition ,2006,26(3):4892494.[6]BOND Y J A ,MUR T Y U S.Graph theory with appli 2cations [M ].New Y ork :Macmillan ,London and Elsevier ,1976.[7]DIETEL R.Graph theory [M ].New Y ork :Spring 2Verlag ,1997.[8]HANSEN P ,MARCO T TE O.Graph coloring and ap 2plication[M ].Rhode Island :AMS Providence ,1999.Adjacent 2V ertex 2Distinguishing Total Chromatic Number of C n ×K nW A N G J i 2S hun 1,L I B u 2j un2(1.Department of mathematics ,Lianyungang Teacher ’s College ,Lianyungang 222006,China2.Department of Mathematics and Physics ,Huaihai Institute of Technology ,Lianyungang 222005,China )Abstract :Let G be a simple grap h.A k 2p roper total coloring of G is called adjacent 2distinguishing if for arbitrary two adjacent vertices u and v ,C (u )≠C (v ),where C (u )is t he set of t he colors of u and ed 2ges which is adjacent to u .The minimum k such t hat G (V ,E )has a k 2adjacent 2vertex 2distinguishing total coloring is called t he adjacent 2vertex 2distinguishing total chro matic number.The adjacent 2vertex 2distinguishing total chromatic number o n t he Cartesion product of circle C m and complete grap h K n (C n×K n )is obtained..K ey w ords :grap h ;total coloring ;adjacent 2vertex 2distinguishing total coloring ;adjacent 2vertex 2distin 2guishing total chromatic number5第1期 王继顺等:C m ×K n 的邻点可区别全染色 。

第 32 卷第 6 期 2016 年 11 月齐 齐 哈 尔 大 学 学 报（自然科学版） Journal of Qiqihar University(Natural Science Edition)Vol.32,No.6 Nov.,2016两类图的笛卡尔积图的临点可区别关联色数董秀芳（江苏财会职业学院，江苏 连云港 222016） 摘要：图的关联着色问题是图着色理论的重要组成部分之一，确定图的关联色数是一个具有很大挑战性也非常有 意义的课题。

非常图的关联色数同图的强色指数有密切的关系，本文给出了路与路的笛卡尔积图和路与完全图的 笛卡尔积图的邻点可区别关联色数。

关键词：笛卡尔积图；关联着色；关联色数 中图分类号：O157.5 文献标志码：A 文章编号：1007-984X(2016)06-0088-02本文讨论的图均是无向、有限、简单图，设 G 二(V,E)是一个图,分别用 V(G)，E(G)，ᇞ(G)， d G ( v ) , N G (v) , V (G ) }表示图 G 的顶点集、边集、最大度，顶点 v 的度 G 中与顶点 v 相邻的顶点集以及顶点集 的度数，在不发生混淆的情况下，可简记为 V,E, ᇞ,d(v)，N（v） ， V ，用 s 表示映射.对于图 G(V,E)， I (G) 表示 G 的关联集，若顶点 v 与边 e 相关联，用(v, e)表示一个关联对，C(v)表示 v 的颜色集， C ( v ) 表示 v 的颜色集的补集，令  表示 I (G) 到颜色集 C 的映射。

定义 1 ： 设 G 和 H 是两个图且 V (G )  u , u ,, u  ， V ( H )  v1 , v2 ,, vn  ， 则 G 和 H 的笛卡尔积图 G  H[5]定义为 V (G  H )  aij aij  ui v j ,1  i  n,1  j  m ， E (G  H )  aij alk i  l且v j vk  E ( H )或j =k 且ui ul  E (G) ， 称 G  H 中的点集 ai1 , ai 2 ,, aim  为第 i 行顶点 (i =1, 2,，n ) 。

若干图的邻点强可区别的E-全染色若干图的邻点强可区别的E-全染色近年来，图论在各个领域得到了广泛的应用，其中一类问题是关于图的染色问题。

图的染色问题涉及将一定数量的颜色分配给图的顶点或边，使得相邻的顶点或边具有不同的颜色。

而邻点强可区别的E-全染色是其中一种较为复杂的染色问题。

邻点强可区别的E-全染色问题定义如下：对于给定的图G=(V,E)，其中 V 是图 G 的顶点集合，E 是图 G 的边集合。

染色是指将一定数量的颜色分配给 V 和 E，使得任意相邻的顶点或边具有不同的颜色。

此外，还要求对于任意u,v∈V，如果uv∈E，那么顶点 u 不能使用邻接点 v 所使用的染色，并且边 uv 不能使用 u 和 v 所使用的染色。

如果图 G 存在一种染色方法满足上述条件，则称图 G 是邻点强可区别的E-全染色。

这种染色问题的研究源于实际生活中的很多应用场景。

例如，电信网络中，在许多无线网络应用中，需要将相邻的节点或边进行染色以区分彼此之间的连通性。

此外，在地图着色问题中，要求相邻地区的边界线以及相连的点使用不同的颜色，以增加地图的可读性。

这些实际应用都可以看作是邻点强可区别的E-全染色问题的一种具体场景。

邻点强可区别的E-全染色问题的求解需要一定的算法和策略。

在研究过程中，学者们提出了许多解决方法。

其中一种常用的方法是使用回溯算法，即从一个起始点出发，依次对图中的顶点和边进行染色，同时满足邻点强可区别的条件。

如果在染色过程中发现无法满足条件，就进行回溯和重新染色。

这种方法的时间复杂度较高，但能够找到满足邻点强可区别的E-全染色。

在实际应用中，邻点强可区别的E-全染色问题的求解往往是一个NP难问题，即不存在多项式时间复杂度的算法可以得到解决方案。

因此，在实践中，通常采用启发式算法或者近似算法来近似求解。

例如，可以通过引入一定的限制条件，降低问题的复杂性，从而找到一个较为满意的染色解。

综上所述，邻点强可区别的E-全染色问题是图论中一个重要且复杂的问题。

图P_m×P_n,P_m×C_n和C_m×C_n的邻点可区别全色数的注记(英文)陈祥恩;张忠辅;孙宜蓉【期刊名称】《数学研究与评论》【年(卷),期】2008(000)004【摘要】Let G be a simple graph. Let f be a mapping from V (G) ∪ E(G) to {1,2,...,k}. Let Cf(v) = {f(v)} ∪ {f(vw)|w ∈ V (G),vw ∈ E(G)} for every v ∈ V (G). If f is a k-proper- total-coloring, and for u,v ∈ V (G),uv ∈ E(G), we haveCf(u) = Cf(v), then f is called a k- adjacent-vertex-distinguishing total coloring (k-AV DTC for short). Let χat(G) = min{k|G have a k-adjacent-vertex-distinguishing total coloring}. Then χat(G) is called the adjacent-vertex- distinguishing total chromatic number (AV DTC number for short)...【总页数】0页(P)【作者】陈祥恩;张忠辅;孙宜蓉【作者单位】College;of;Mathematics;and;Information;Science;Northwest;Normal;Univers ity;Institute;of;Applied;Mathematics;Lanzhou;Jiaotong;University【正文语种】中文【中图分类】O157.5【相关文献】1.笛卡尔积图P_m×K_n及C_m×K_n的邻点可区别E-全染色研究 [J], 董秀芳2.关于图P_m×P_n的邻点可区别全染色 [J], 段广森3.P_m×K_n的邻点可区别全色数(英文) [J], 陈祥恩;张忠辅4.P_m∨C_n的点可区别边色数 [J], 李敬文;徐保根;李沐春;张忠辅;赵传成;任志国5.嵌套图C_n×P_m(n≥3,m=2,3)的点-平衡指数集 [J], 姬玉荣;刘金萌因版权原因，仅展示原文概要，查看原文内容请购买。

第35卷第1期河南师范大学学报!自然科学版"V ol .34No .12006年2月J o rnal o f ~enan Nor m al UniUersit $!Nat ral Science "Feb .2006文章编号!1000-2367 2006 01-0139-03关于几类图的邻点可区别全染色李光海#李武装安阳师范学院数学系 河南安阳455002摘要!图的邻点可区别全染色是最近提出的新概念.本文给出了风车图K t 3 齿轮图 Wn 和图D m 4以及D m n 和F m n 的邻点可区别全色数.关键词!图 染色 邻点可区别 全色数中图分类号!0157.5文献标识码!A图的染色问题具有重要实际意义和理论意义.近年来这一方面的研究非常活跃.Burris AS 和S chel p R ~ 1研究了点可区别的正常边染色 张忠辅教授等在文献 2 中提出了图的邻强边染色的概念 最近他们又提出了图的邻点可区别全染色的概念 3 受到图论界的关注.本文所讨论的图G 均为有限无向简单图 用V G E G 分别表示G 的点 边集合 A G 表示G 的最大度.定义1"3#设G 是阶至少为2的连通图 a 是正整数 f 是VG E G 到 1 2 a 的映射 对 V G 记C = f f U U E G .如果: 1 对任意 U Uw E G w 有f U f Uw 2 对任意 U E G 有f f U f f U fU f U 3 对任意 U E G 有C C U 那么称f 为G 的a-邻点可区别全染色 简记为a -AVDC 称m i n a G 有a-邻点可区别全染色 为G 的邻点可区别全色数 记作x a tG .本文研究了图K t 3 D m 4及 Wn F m n 的邻点可区别全染色.定义2由t 个完全图K 3恰有一个公共点构成的图称为K t 3.定义3由m 个4回路恰有一个公共点构成的图记为D m 4.定义4在轮W n 的轮圈C n 上 每相邻点之间都加入一个顶点后所得到的图称为齿轮图 记作 Wn .1主要结论及证明定理1风车图K t 3 x a t K t 3 =2t +1证明K t 3中公共点记为J 0 每一个K 3中另两点记为J i $i i =1 2 t .由6 J 0 =2t 知x a t K t 3 Z 2t +1.下证x a t K t 3 S 2t +1 为此仅需证明K t 3存在2t +1-AVD C 即可.如下定义一个从V K t 3 E K t 3 到 1 2 2t +1 的映射f :f J i J o =2i _1 f $i J o =2i i =1 2 t f J i =2i _3 f $i =2i _2 i =2 3 t f J 1 =2t _1 f $1 =2t fJ o =2t +1 f J i $i =2t +1 i =1 2 t .显然f 是K t3的2t +1-全染色.另外有CJ 0 = 1 2 2t 2t +1C J i = 2i _3 2i _1 2t +1 i =2 tC $i = 2i _2 2i 2t +1i =2 t C J 1 =2t _1 2t +1 1C $1 = 2t 2t +1 2 .显然C J 0 C J i C J 0 C $ii =1 2 t .收稿日期!2005_04_12作者简介!李光海 1964_ 男 河南罗山人 安阳师范学院讲师 主要从事数学教学方面的工作.由上知C (J i ) C ($i ) i =1 2 t .故f 是K t 3的2t +1-AVD C .因此x a t (K t 3)=2t +1.定理2对于图D m 4有x a t (D m 4)=2m +1.证明记D m 4中C 4的公共点为J 0 每一个4圈中其它3点记为J i $i i 其中J i 与$i 不相邻.D m 4中6(J 0)=2m .显然x a t (D m 4)Z 2m +1.下证x a t (D m 4)S 2m +1为此仅需证明D m 4存在2m +1-AVD C 即可.如下定义一个从V (D m 4) E (D m 4)到 1 2 2m +1 的映射ff (J 0J i )=2i _1i =1 2 m f (J 0$i )=2ii =1 2 m f (J ii )=2i _3 i =2 3 m f ( i $i )=2i _2i =2 3 m f (J 1 1)=2m _1 f ( 1$1)=2m f (J 0)=2m +1 f (i )=2m +1 i =1 2 m f (J i )=2i _5 f ($i )=2i _4i =3 4 m f (J 1)=2m _3 f ($1)=2m _2f (J 2)=2m _1 f ($2)=2m.显然f 是D m 4的2m +1-全染色 另外有C (J 0)=1 2 2m C (J i )= 2i _5 2i _3 2i _1 i =3 4 mC ($i )= 2i _4 2i _2 2i i =3 4 m C (J 1)= 1 2m _3 2m _1 C (J 2)= 3 1 2m _1 C ($1)= 2 2m _2 2mC ($2)= 2 4 2m C ( i )= 2i _3 2i _2 2m +1 i =2 3 m .C ( 1)=2m _1 2m 2m +1 .显然C (J 0) C (J i ) C (J 0) C ($i ) i =3 4 m .由上可知C (J i ) C ( i ) C ( i ) C ($i ) i =1 2 m .故f 是D m 4的2m +1-AVD C .因此x (D m 4)=2m +1.由定理1及定理2 可以推知一般的m 个n 回路恰有一个公共点构成的图D m n 的邻点可区别全染色数为2m +1.规律同定理1及定理2.定理3对于齿轮图 Wn 有x a t ( W n )=n +1.证明各顶点记号如图3.由于最大度顶点J 0 6(J 0)=n所以x a t ( Wn )Z n +1.下证x a t ( W n )S n +1.为此仅需证明 W n 存在n +1-AVD C 即可.如下定义一个从V ( W n ) E ( Wn )到 1 2 n +1 的映射f f (J 0)=n +1 f ($i )=n +1i =1 2 n f (J 0J i )=ii =1 2 n f (J i )=i _1i =2 3 n f (J 1)=n .f (J i $i )=i +1i =1 2 n _1 f (J n $n )=1f ($i J i +1)=i _1i =2 3 n _1f ($n J 1)=n _1f ($1J 2)=nJ i $i 与边$i J i +1 J i J 0 J i $i _1相邻(i =2 3 n _1) 而J 1$1与$1J 2 J 1J 0 J 1$n 相邻 J n $n 与J 1$n J n $n _1 J n J 0相邻 都标不同颜色 且邻点颜色也不同 关联的点 边的颜色也不相同 故f 是一个n +1-全染色.又邻点度数不同 故C ( ) C (U )U V ( W n ).故f 是 W n 的n +1-AVD C .故x a t ( W n )=n +1.定理4对于图D m n 有x a t (D m n )=2m +1(m Z 2).证明D m n 是由m 个n 圈恰有一个公共点构成.显然A (D m n )=2m .故x a t (D m n )Z 2m +1.又由文献3 知 圈C n (n Z 4) 有x a t (C n )=4<2m +1 故x a t (D m n )=2m +1.定理5对于图F m n 有x a t (F m n )=m (n _1)+1(m Z 2 n Z 4).证明F m n 是由m 个完全图K n 恰有一个公共点构成.显然A (F m n )=m (n _1) 故x a t (F m n )Z m (n _1)+1.又由文献 3 对于完全图K n 有x a t (K n )=n +1 n E 0(mOd 2)n +2 n E 1(mOd 2)显然n +1S m (n _1) n +2S m (n _1) 故x a t (F m n )=m (n _1)+1.!下转第154页"2张荣祖.中国动物地理M.北京科学出版社1999.3赵尔宓黄美华宗愉等.中国动物志爬行纲第3卷有鳞目蛇亚目M.北京科学出版社1998.4袁秀珍魏传斌.湖北省蛇类新记录J.武汉教育学院学报200019325-27.5王文毅王春东郑海强等.海南岛蛇类新记录黑背白环蛇J.海南师范学院学报自然科学版200316193 -94.6罗健高红英周元媛.重庆市爬行动物物种多样性研究及保护J.四川动物2004233249-256.7宋鸣涛.陕西省爬行动物区系及地理区划J.四川动物2002213146-148.8姚崇勇.甘肃省爬行动物区系及地理区划J.四川动物2004233217-221.9张盛周陈壁辉.安徽省爬行动物区系及地理区划J.四川动物2002213136-141.10陈壁辉.安徽两栖爬行动物志M.合肥安徽科学技术出版社1991.11王宁郑光美.北京市爬行动物新纪录黑背白环蛇J.四川动物2005244489.L y codon r uhst r ati A Ne W Record of S nake i n H enan Provi nceC~EN X i aO-hOn g Z~M i n g-Wei TA0L i-kuiCOll e g e Of L if e S ci ences~enan NOr m al ni versit y X i nXi an g453007Chi naAbstract A s p eci es Of g enus L$co6on COl ubri dae Fa m il y Was cOll ected f r O m Shan g chen g COunt y~enan Pr Ovi nce On M a y2004Which Was i dentifi ed as L$co6on r hst rati.Ke y Words L$co6on r hst rati ne W recOr d~enan Pr Ovi nce!上接第140页"参考文献1Burri s A C S chel p R~.Vert eX-di sti n g ui shi n g p r O p er ed g e-cOl Ori n g J.J Of G ra p h t heOr y19772173-82.2Zhan g ZhOn g f u L i u L i nZ hOn g W an g Ji anf an g.Ad acent str On g ed g e cOl Ori n g Of g ra p hs J.A pp li ed M at he m ati cs Lett ers200215623-626.3Zhan g ZhOn g f u.0n t he ad acent vert eX-di sti n g ui shi n g t Ot al cOl Ori n g Of g ra p hs J.中国科学2005483289-299.On t he Adi acent Vertex-disti n g uishi n g Tot al Col ori n g of S ever of C l asses G ra p hsLI Guan g-hai LI W u-Zhuan gD e p t.Of M at hs An y an g T eachers COll e g e An y an g455002Chi naAbsrt act Recentl y sO m e p eO p l e p resented t he cOnce p t Of ad acent verteX-disti n g uishi n g t Otal cOl Ori n g Of g ra p h.In t his p a p er We p r Oved t hat x a t K t3=2t+1x a t D m4=2m+1x a t W n=n+1x a t D m n=2m+1m Z2x a t F m n=m n_1+1 m Z2n Z4.Ke y Words g ra p h cOl Ori n g t he adi acent V erteX-disti n g uishi n g t Otal cOl Ori n g nu mber。

几类图的D（2）-点可区别染色几类图的D（2）-点可区别染色摘要：D（2）-点可区别染色是指在一个图中，相邻两个点所相交的边的颜色是不同的。

本文将探讨几类特殊图的D （2）-点可区别染色问题，包括完全图、路径图、环图、树图和平面图。

通过对每种图的结构和特性分析，得出了它们的D （2）-点可区别染色的性质和方法。

1. 引言在图论中，D（2）-点可区别染色是一种常见的染色问题。

它与传统的图的染色问题略有不同，要求在染色过程中相邻两个点所相交的边的颜色是不同的。

这种染色问题在实际应用中有着广泛的应用，如地图上的区域着色、任务分配等。

因此，了解各类图的D（2）-点可区别染色的特性和方法对我们解决实际问题具有重要意义。

2. 完全图的D（2）-点可区别染色完全图是指每两个不同的顶点之间都有一条边相连的图。

对于完全图，由于每个顶点都与其他所有顶点相连，因此无法实现D（2）-点可区别染色。

3. 路径图的D（2）-点可区别染色路径图是指顶点之间仅有一个公共边的连续顶点集。

在路径图中，我们可以通过交替染色法实现D（2）-点可区别染色。

具体方法是从起始顶点开始，依次交替染色，即相邻两个顶点的颜色不同。

4. 环图的D（2）-点可区别染色环图是指所有顶点之间通过边相连而构成一条闭合回路的图。

对于环图，我们可以使用交替染色法实现D（2）-点可区别染色，具体方法与路径图相同。

此外，我们还可以使用数学归纳法证明环图的D（2）-点可区别染色。

5. 树图的D（2）-点可区别染色树图是指无环连通图，其中任意两个顶点之间有唯一路径相连。

树图的D（2）-点可区别染色非常简单，只需要对根节点进行染色，然后依次向下染色，每次染色时选择一个未被染色的颜色即可。

6. 平面图的D（2）-点可区别染色平面图是指可以被嵌入到二维平面上的图。

对于平面图，我们可以使用四色定理来实现D（2）-点可区别染色。

四色定理指出，任何一个地图都可以使用四种颜色进行着色，使得任意相邻的两个地区颜色不同。