有向图的邻点可区别弧染色.pdf

第3 6卷 第2期2023年05月 青 岛 大 学 学 报(自 然 科 学 版)J O U R N A LO FQ I N G D A OU N I V E R S I T Y(N a t u r a l S c i e n c eE d i t i o n)V o l.3 6N o.2M a y2023 文章编号:1 0 0 6 1 0 3 7(2 0 2 3)0 2 0 0 0 1 0 4d o i:1 0.3 9 6 9/j.i s s n.1 0 0 6 1 0 3 7.2 0 2 3.0 2.0 1有向图的邻点可区别弧染色季 强,王纪辉(济南大学数学科学学院,济南2 5 0 0 2 2)摘要:研究了有向图的邻点可区别弧染色,证明了每个有向图D都有-,+(D)*(D)+2。对于完全有向图,完全对称二部有向图和有向树,给出了邻点可区别弧染色数的更精确结果。关键词:有向图;邻点可区别弧染色;特殊有向图中图分类号:O 1 5 7.5 文献标志码:A收稿日期:2 0 2 2-1 1-0 4基金项目:国家自然科学基金(批准号:1 2 0 7 1 3 5 1)资助;山东省自然科学基金(批准号:Z R 2 0 2 0 MA 0 4 3)资助。通信作者:王纪辉,男,博士,教授,主要研究方向为图论及其应用。E-m a i l:s s_w a n g j h u j u.e d u.c n1 引言及预备知识本文仅考虑简单有限有向图。设D=(V(D),A(D)是简单有向图,d-(v)和d+(v)分别表示有向图D中顶点v的入度邻点集和出度邻点集的大小,也称为顶点v的入度和出度。+(D)和-(D)分别表示有向图D的最大出度和最大入度,令*(D)=m a x+(D),-(D)1。有向图D的一个正常k-弧染色是一个映射f:A(D)0,1,k-1 使得D中有公共起点的弧染不同颜色,有公共终点的弧染不同颜色2。有向图D正常弧染色的最小颜色数记为(D)。S-(v)和S+(v)分别表示顶点v的入度弧和出度弧在染色f下所染的颜色集。2 0 1 6年L i等3把无向图的点可区别边染色推广到有向图,提出了有向图的点可区别弧染色的概念。若有向图D的正常弧染色f使得对D中任意两个顶点u,v,都有S-(u)S-(v)且S+(u)S+(v)成立,则称f是点可区别的。2 0 1 9年,S o p e n a等4改进并提出一种新的有向图的点可区别弧染色,若有向图D的正常弧染色f使得对D中任意两个顶点u,v,都有(S-(u),S+(u)(S-(v),S+(v),即S-(u)S-(v)或S+(u)S+(v)成立,则称f是点可区别的;若对D中任意两个相邻的顶点u,v,都有S-(u)S-(v)或S+(u)S+(v)成立,则称f是邻点可区别的。本文推广并研究了有向图的邻点可区别弧染色。若有向图D的正常弧染色f使得对D中任意有向弧u v,顶点u的入度弧和v的出度弧的颜色集不同,即S-(u)S+(v)成立,则称f是邻点可区别的。有向图D邻点可区别弧染色的最小颜色数记为-,+(D)。如果有向图D中存在有向弧u v,其中u是一个源顶点(即d-(u)=0),v是一个接收点(即d+(v)=0),这样的有向弧称为s s-弧5。显然,若D中含有s s-弧,则其邻点可区别弧染色没有意义,因此,在研究有向图的邻点可区别弧染色时,只考虑至少有三个顶点且不含s s-弧的有向图。由邻点可区别弧染色的定义得到命题1。命题1 对任意的有向图D,-,+(D)(D)=*(D)。若D中存在有向弧u v满足d-(u)=d+(v)=*(D),则-,+(D)*(D)+1。2 一般有向图的邻点可区别弧染色对每个有向图D=(V(D),A(D),定义相应的平衡二部图为BD=(X,Y;E),其中青 岛 大 学 学 报(自 然 科 学 版)第3 6卷X=Y=V(D),E(BD)=u v:uX,vY,u vA(D)设X(BD)和Y(BD)是X和Y中的顶点最大度,有+(D)=X(BD),-(D)=Y(BD),(BD)=m a xX(BD),Y(BD),*(D)=(BD)=m a xX(BD),Y(BD)。有向图D的正常弧染色等价于相应二部图BD的正常边染色。因此,得到引理1。引理1 设D是有向图,则(D)=(BD)=(BD)=*(D)。S(u)表示顶点u关联的边在正常边染色c下所染的颜色集。如果二部图B=(X,Y;E)存在正常边染色c,对于X中任意顶点u和Y中任意顶点v相邻,有S(u)S(v),称二部图B的边染色c是邻点可区别的。二部图B邻点可区别边染色的最小颜色数记为a(B)。观察到有向图D的邻点可区别弧染色等价于相应二部图BD的邻点可区别边染色,得到引理2。引理2 设D是有向图,则-,+(D)=a(BD)。在二部图B中,令(B)=m a xX(B),Y(B)。B a l i s t e r等6给出了二部图B的邻点可区别边染色的一个上界。引理36 如果B是不含孤立边的二部图,那么a(B)(B)+2。对任意有向图D,有-,+(D)=a(BD)(BD)+2=*(D)+2。因此,应用引理3得到有向图的邻点可区别弧染色数的一般上界。定理1 设D是有向图,则-,+(D)*(D)+2。考虑有向圈Ck(k4n,nN*),*(Ck)=1,很明显-,+(Ck)=3=*(Ck)+2。对一般的有向图,定理1中邻点可区别弧染色数的上界*(D)+2是紧的。3 某些特殊有向图的邻点可区别弧染色现主要研究有向路和有向圈,完全有向图,完全对称二部有向图和有向树的邻点可区别弧染色数。3.1 有向路和有向圈定理2 对有向路Pk,若k3,则-,+(Pk)=2=*(Pk)+1。证明:设有向路Pk为v1v2vk。由命题1,知-,+(Pk)*(Pk)+1=2。令f:A(Pk)0,1,按照0,0,1,1的染色顺序依次对每个有向弧进行染色,对任一有向弧vivi+1A(Pk)(i=2,3,k-2),顶点vi的入度弧与vi+1的出度弧颜色不同,从而染色f是Pk的邻点可区别弧染色,所以-,+(Pk)*(Pk)+1=2,即-,+(Pk)=2=*(Pk)+1。定理3 对有向圈Ck,若k3,则-,+(Ck)=2=*(Ck)+1,k0(m o d4)3=*(Ck)+2,其他证明:设有向圈Ck为v1v2vkvi,每个顶点viV(Ck),d-(vi)=d+(vi)=1,*(Ck)=1。如果k0(m o d4),即k=4n(nN*)。由命题1,-,+(Ck)*(Ck)+1=2。令f1:A(Ck)0,1。按照0,0,1,1的染色顺序从有向弧v1v2开始依次对每个有向弧进行染色,这样对任一有向弧vivjA(Ck),顶点vi的入度弧与vj的出度弧颜色不同,从而染色f1是Ck的邻点可区别弧染色,所以-,+(Ck)*(Ck)+1,即-,+(Ck)=2=*(Ck)+1。如果k0(m o d4),即k4n(nN*),令f2:A(Ck)0,1,2,f2(vivj)=im o d3,即有向弧vivj染im o d3色。对任一有向弧vivjA(Ck),顶点vi的入度弧与vj的出度弧颜色不同,因此染色f2是Ck的邻点可区别弧染色,即-,+(Ck)=3=*(Ck)+2。定理得证。3.2 完全有向图设K*n表示底图是完全图Kn的完全对称有向图,如果c为Kn的任一正常边染色,定义K*n的弧染色f为f(u v)=f(v u)=c(u v),其中u vE(Kn)。如果Kn在染色c下的边染色是邻点可区分的,即任意相2 第2期 季 强等:有向图的邻点可区别弧染色邻的顶点u,vV(Kn),u,v关联的颜色集不同,那么f是K*n的邻点可区别弧染色7。因此,完全对称有向图K*n的弧染色是邻点可区分的当且仅当底图Kn的边染色是邻点可区分的。定理4 对顶点数n3的完全对称有向图K*n,则-,+(K*n)=*(K*n)+1=n。证明:设V(K*n)=v0,v1,vn-1,由命题1,对顶点数n3的K*n,有-,+(K*n)*(K*n)+1=n。情况1 n是奇数。把Kn划分成n个边不交 的最大匹配M0,M1,Mn-1,使得对 任意的i0,n-1,顶点vi与匹配Mi中的任意边都不关联。设f是K*n的一个弧染色,且满足对任意的i,j0,n-1,若边vivjMk,则f(vivj)=f(vjvi)=k。显然,顶点vi与颜色i是不关联的。因此,对于K*n中任一有向弧vivj,有S-(vi)S+(vj),所以K*n的n-弧染色f是邻点可区别的,即-,+(K*n)=*(K*n)+1=n。情况2 n是偶数。设由K*n的顶点集v0,v1,vn-2 导出的子图为K,由情况1得K 存在一个邻点可区别的(n-1)-弧染色f。下面使用n种颜色0,1,n-1 把f 拓展为K*n的n-弧染色f:(1)任意顶点vi和vj,ji+1(m o dn-1),0ijn-2,令f(vivj)=f(vivj);(2)任意顶点vi,0in-2,令f(vivi+1)=n-1,f(vi+1vi)=f(vi+1vi)(下标模n-1);(3)任意顶点vi,0in-2,令f(vn-1vi)=f(vi-1vi),f(vivn-1)=f(vi+1vi)。因为顶点vi不关联染颜色i的弧,即iS-(vi)S+(vi),所以对任意有向弧vivjA(K*n),有S-(vi)S+(vj)。因此,f是K*n的邻点可区别弧染色,即-,+(K*n)n。因此,-,+(K*n)=*(K*n)+1=n,定理得证。由定理4得到底图是完全图的有向图的邻点可区别弧染色数。推论1 如果有向图D的底图是完全图,那么-,+(D)=*(D)+1。3.3 完全对称二部有向图定理5 对完全对称二部有向图K*m,n,若m2,n2,则-,+(K*m,n)=*(K*m,n),mn*(K*m,n)+2,m=n证明:设K*m,n的两部分顶点集为u1,u2,um 和v1,v2,vn。情况1 mn。不妨设mn。使用n种颜色0,1,n-1 定义Km,n的邻点可区别n-边染色c,令c(uivj)=i+j(m o dn),(0im-1,0jn-1),相应的K*m,n弧染色f定义f(uivj)=f(vjui)=c(uivj)。对于K*n中任一有向弧uivj,有S-(ui)S+(vj),K*m,n的n-弧染色f是邻点可区别的。因此,-,+(K*m,n)=n=*(K*m,n)。情况2 m=n。不妨设K*m,n的两部分顶点集为u1,u2,un 和v1,v2,vn。使用n+2()种颜色0,1,n,n+1定义Kn,n的邻点可区别边染色c,令c(u1vj)=j,c(uivj)=i+j(m o dn+2),相应的弧染色f为f(uivj)=f(vjui)=c(uivj),从而f是K*n,n的邻点可区别弧染色,所以-,+(K*n,n)n+2=*(K*n,n)+2。因此,-,+(K*m,n)=*(K*m,n),mn*(K*m,n)+2,m=n。3.4 有向树定理6 设D是最大度为*(D)的有向树。如果D中存在有向弧u v满足d-(u)=d+(v)=*(D),那么-,+(D)=*(D)+1;否则,-,+(D)=*(D)。证明:设D是顶点n3个数的有向树,D的底图u n d(D)是树。如果D的底图u n d(D)是星或路,定理成立。若D中不存在有向弧u v满足d-(u)=d+(v)=*(D),则-,+(D)=*(D)。设D中存在有向弧u v满足d-(u)=d+(v)=*(D),那么-,+(D)*(D)+1。设P=v1v2vk(kn)是u n d(D)中的3青 岛 大 学 学 报(自 然 科 学 版)第3 6卷最长路。令D=D-vk,所以*(D)=*(D)。假设D-v存在使用*(D)+1种颜色的邻点区别弧染色f。下面证明使用*(D)+1种颜色可把f拓展为有向树D的邻点可区别弧染色。不妨设点vk-1和vk间的有向弧为vk-1vk。根据P的极大性,那么vk-1会有一个邻点vk-2不是叶子,不妨设vk-2恰为vk-1的入度邻点。因为d-(vk-2)*(D),d+(vk-1)*(D),所以可能出现矛盾的是vk-2的入度和vk-1的出度相等的情况。若d-(vk-2)=d+(vk-1)=*(D),用*(D)+1色给弧vk-1vk染色,有S-(vk-2)S+(vk-1)。若d-(vk-2)*(D),d+(vk-1)*(D),使用vk-2顶点入度弧中未使用的颜色a给弧vk-1vk染色即可,此时S-(vk-2)S+(vk-1)。通过这样的染色方式得到了有向树D的邻点可区别弧染色,所以-,+(D)*(D)+1。因此,如果D中存在有向弧u v满足d-(u)=d+(v)=*(D),那么-,+(D)=*(D)+1;否则,-,+(D)=*(D)。定理得证。参考文献1B AN G-J E N S E NJ,GUT I NGZ.D i g r a p h s:T h e o r y,a l g o r i t h m sa n da p p l i c a t i o n sM.B e r l i n:S p r i n g e rS c i e n c ea n dB u s i n e s sM e d i a,2 0 0 8.2WE S TDB.I n t r o d u c t i o nt og r a p ht h e o r yM.U p p e rS a d d l eR i v e r:p r e n t i c eH a l l,2 0 0 1.3L IH,B A IYD,HE W H,e t a l.V e r t e x-d i s t i n g u i s h i n gp r o p e ra r cc o l o r i n g so fd i g r a p h sJ.D i s c r e t eA p p l i e dM a t h e m a t i c s,2 0 1 6,2 0 9:2 7 6-2 8 6.4S O P E NAE,WO ZN I AK M.An o t eo nt h en e i g h b o u r-d i s t i n g u i s h i n gi n d e xo fd i g r a p h sJ.A r sM a t h e m a t i c aC o n t e m p o r a n e a,2 0 2 3,2 3(1):1-7.5B E N S MA I LJ,L YN G S I EK.1-2-3C o n j e c t u r e i nd i g r a p h s:M o r er e s u l t sa n dd i r e c t i o n sJ.D i s c r e t eA p p l i e dM a t h e m a t i c s,2 0 2 0,2 8 4:1 2 4-1 3 7.6B A L I S T E RPN,G YO R IE,L EHE LJ,e t a l.A d j a c e n t v e r t e xd i s t i n g u i s h i n ge d g e-c o l o r i n g sJ.S I AMJ o u r n a l o nD i s c r e t eM a t h e m a t i c s,2 0 0 7,2 1(1):2 3 7-2 5 0.7Z HAN GZF,L I ULZ,WAN GJF.A d j a c e n t s t r o n ge d g ec o l o r i n go fg r a p h sJ.A p p l i e dM a t h e m a t i c sL e t t e r s,2 0 0 2,1 5(5):6 2 3-6 2 6.N e i g h b o r-d i s t i n g u i s h i n gA r cC o l o r i n g so fD i g r a p h sJ IQ i a n g,WANGJ i-h u i(S c h o o l o fM a t h e m a t i c a lS c i e n c e s,U n i v e r s i t yo f J i n a n,J i n a n2 5 0 0 2 2,C h i n a)A b s t r a c t:N e i g h b o r-d i s t i n g u i s h i n ga r cc o l o r i n go fd i g r a p h sw a ss t u d i e d.I tw a sp r o v e dt h a tf o re v e r yd i-g r a p hD,-,+(D)*(D)+2.F o rs o m es p e c i a ld i g r a p h s,s u c ha sc o m p l e t ed i g r a p h s,c o m p l e t es y m-m e t r i cb i p a r t i t ed i g r a p h s a n dd i r e c t e d t r e e s,t h e i rn e i g h b o r-d i s t i n g u i s h i n ga r c c h r o m a t i cn u m b e rw a sg i v e n.K e y w o r d s:d i g r a p h;n e i g h b o r-d i s t i n g u i s h i n ga r cc o l o r i n g;s p e c i a l d i g r a p hc l a s s e s4