TOPICS
Search

Local Antimagic Labeling


A local antimagic labeling of a finite simple graph G=(V,E) with m>=1 edges is a bijection f:E->{1,2,...,m} for which adjacent vertices have distinct induced labels (Arumugam et al. 2017). The induced label of a vertex v is

 f^+(v)=sum_(e∋v)f(e),

where the sum runs over the edges incident to v.

The induced labels give a proper coloring of the vertices. The minimum number of colors obtainable in this way is the local antimagic chromatic number. In contrast, an antimagic graph requires the induced labels at all vertices to be distinct, including nonadjacent pairs.

A graph admitting a local antimagic labeling is called a local antimagic graph. Every connected graph with at least three vertices admits a local antimagic labeling (Haslegrave 2018). The complete graph K_2 does not, since its two vertices receive the same label from their single edge.


See also

Antimagic Graph, Labeled Graph, Local Antimagic Chromatic Number, Local Antimagic Graph, Vertex Coloring

Explore with Wolfram|Alpha

References

Arumugam, S.; Premalatha, K.; Bača, M.; and Semaničová-Feňovčíková, A. "Local Antimagic Vertex Coloring of a Graph." Graphs Combin. 33, 275-285, 2017. https://doi.org/10.1007/s00373-017-1758-7.Haslegrave, J. "Proof of a Local Antimagic Conjecture." Disc. Math. Theor. Comput. Sci. 20, #18, 2018. https://doi.org/10.23638/DMTCS-20-1-18.

Cite this as:

Weisstein, Eric W. "Local Antimagic Labeling." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LocalAntimagicLabeling.html

Subject classifications