繁星的局部反魔幻着色数  

Local antimagic chromatic number of blossomed star

作　　者：杨雪 边红[1] 于海征[2] 刘丹丹 YANG Xue;BIAN Hong;YU Haizheng;LIU Dandan(School of Mathematical Sciences,Xinjiang Normal University,Urumqi 830017,China;College of Mathematics and System Sciences,Xinjiang University,Urumqi 830046,China)

机构地区：[1]新疆师范大学数学科学学院,新疆乌鲁木齐830017 [2]新疆大学数学与系统科学学院,新疆乌鲁木齐830046

出　　处：《厦门大学学报（自然科学版）》2024年第6期1082-1088,共7页Journal of Xiamen University：Natural Science

基　　金：国家自然科学基金(12361072,11971406);2023西藏自治区自然科学基金面上项目(2023D01A36);2023西藏自治区自然科学基金青年项目(2023D01B48);2024新疆师范大学研究生创新基金(XSY202401025);2022新疆师范大学创新团队(XJNU2022)。

摘　　要：[目的]图G=(V(G),E(G))是连通简单图且|V(G)|=n,|E(G)|=m.本文研究图的局部反魔幻着色.[方法]图G的局部反魔幻标号是一个双射f:E(G)→{1,2,…,m},使得对图G的任意两个相邻的顶点u和v都有其点权和互异,即ω(u)≠ω(v),其中ω(u)=∑e∈E(u)f(e),E(u)是与点u相关联的边的集合.若对图G的顶点x着颜色ω(x),显然,G的任一个局部反魔幻标号自然导出图G的一个正常点着色.图G的局部反魔幻着色数是其局部反魔幻标号中所用的最少颜色数,记为χla(G).称一棵树T为繁星,如果它可以通过在星形树的悬挂点上添加一些悬挂边而得到.令T_(n,m)表示星形树S 1,n的每条悬挂点上添加m条悬挂边而得到的繁星.将局部反魔幻着色应用于繁星图,根据繁星图的结构进行分类讨论,逐步确定局部反魔幻标号,尽可能使用与繁星图的悬挂边数量相近的颜色数,以求得相应的局部反魔幻着色数.[结果]对于繁星T_(n,m),有(1)当n>2m+1或n=2,m(m≥4)是偶数时,χla(T_(n,m))=mn+2;(2)当m是奇数且n≤2m+1;或m=2,n=2,4;或m是偶数,n是奇数且n≤2m+1;或m,n(m,n≥4)是偶数且n=m,m+2时,χla(T_(n,m))=mn+1;(3)当m,n(m≥4,n≥4)是偶数且n≠m,m+2时,mn+1≤χla(T_(n,m))≤mn+2.[结论]对繁星图进行局部反魔幻着色并得到了其局部反魔幻着色数.[Objective]As a connected simple graph,graph G=(V(G),E(G))is followed by|V(G)|=n,|E(G)|=m.In this paper,the local antimagic coloring of graphs is studied.[Methods]A bijection f:E(G)→{1,2,…,m}is called a local antimagic labeling of G such thatω(u)≠ω(v)for any two adjacent vertices u and v in G,whereω(u)=∑e∈E(u)f(e),and E(u)is the set of edges incident to u.Clearly,any local antimagic labeling induces a proper vertex coloring of G,where the vertex x is assigned the colorω(x).The local antimagic chromatic number,denoted byχla(G),is the minimum number of colors taken over all colorings induced by the local antimagic labelings of G.A tree T is called a blossomed star graph if it can be obtained by adding some pendant edges to the pendant vertices of a star tree.Let T_(n,m) denote the blossomed star obtained by adding m pendant edges to every pendant vertex of the star tree S 1,n.The local antimagic coloring is applied to the blossomed star graph,and the local antimagic labeling is determined step by step according to the structure of the blossomed star.Finally,the color number close to the number of pendant edges of the blossomed star is used as far as possible to obtain the corresponding local antimagic chromatic number.[Results]For the blossomed star T_(n,m),we find that(1)χla(T_(n,m))=mn+2 when n>2m+1;or n=2,even m(m≥4);(2)χla(T_(n,m))=mn+1 when m is odd and n≤2m+1;or m=2,n=2,4;or even m,odd n and n≤2m+1;or even m,n(m,n≥4)and n=m,m+2;(3)mn+1≤χla(T_(n,m))≤mn+2 when m,n(m≥4,n≥4)are even and n≠m,m+2.[Conclusion]The local antimagic coloring is performed on the blossomed star graph and the local antimagic chromatic number is obtained.

关 键 词：局部反魔幻标号 局部反魔幻着色数 繁星 

分 类 号：O157.5[理学—数学]