基于图运算的局部反魔幻着色数的研究

Research on the Local Antimagic Chromatic Number Based on Graph Operations

令 G = (V (G), E(G)) 是有 n 个顶点和 m 条边的简单连通图。一个双射 f : E(G) → {1, 2, ···, m} 称为图 G 的一个局部反魔幻标号,如果对于图 G 中的任意两个相邻的顶点 u 和 v 满足 ω(u)≠ω(v),这里,其中 E(u) 是与点 u 相关联的边的集合。如果给图 G 中任意一个顶点 v 着颜色 ω(v),那么图 G 的任意一个局部反魔幻标号都会导出图 G 的一个正常点着色。图 G 的局部反魔幻着色数 χla(G) 是图 G 的局部反魔幻标号所导出的所有着色中的最少颜色数。本文主要研究经过一些图运算(如:友谊图加一条悬挂边 Fn + {e} 和一些特殊图星图 Pm(Sn) 和双星图 Pm(Sl,q) 的剖分图)之后图的局部反魔幻着色问题。

Let G = (V (G), E(G)) be a simple connected graph with |V (G)| = n and |E(G)| = m. A bijection f : E(G) → {1, 2, . . . , m} is called local antimagic labeling if for any two adjacent vertices u and v, ω(u)≠ω(v), where , and E(u) is the set of edges incident to u. Thus any local antimagic labeling induces a proper vertex coloring  of G, where the vertex u is assigned the color ω(u). The local antimagic chromatic number χla(G) is the minimum number of colors taken over all colorings induced by local antimagic labelings of G. In this paper, we study the exact values of the local antimagic chromatic numbers of some graphs based graph operation, such as Fn + {e} , where e is a pendant edge adding to Fn and the sub-divided graphs Pm(Sn) and Pm(Sl,q) of some special graphs.