一类新的魔术染色

摘要

借鉴于Kotzig和Rosa在1970年定义的边魔术全标号,我们给具有P个顶点和q条边的图G定义了一个新的染色标号,叫作k-魔术染色f,其中f是一一映射-V(G)∪E(G)→{1,2,…,p+q},使得任何边uv∈E(G)满足f(u)+f(v)=k+f(uv),并得到超级k-魔术染色的概念.我们得到了一些具有k-魔术染色或超级k-魔术染色图的性质以及构造这些图的方法.最后,我们猜测所有的树具有一个超级k-魔术染色.%Motivated from the edge-magic total labelling defined by Kotzig and Rosa(1970),we define a nearly k-magic coloring f of a graph G with p vertices and q edges that is a bijection from V(G) ∪ E(G) to {1, 2,…,p + q} such that |f(u) + f(v) - f(uv)|≤ k whenever uv ∈ E(G). We have some results on a k-magic coloring f of G which is a nearly k-magic coloring of G and keeps f(u) + f(v) = k + f(uv) for uv ∈ E(G). Furthermore, we study some graphs with a supper k-magic coloring f that is k-magic coloring and f(u) ≤ p for all u ∈ V(G). We find some ways to construct some graphs having k-magic coloring or supper k-magic coloring, and show some properties about such graphs. At the end of this paper, we conjecture that any tree has a supper k-magic coloring.