Draft:Magic Labelings

  • Comment: There isn't a lead section, nor a gentle introduction to some of the concepts that follow, so it's not really looking like an entry into an encyclopedia. Imagine someone new to this topic, maybe they won't get to the end of the article but they should at least be able to start reading it.
    I hope this was not written using LLM / AI /chatgpt, since that is not allowed for articles starting from scratch. Some of the sources do not go to the full abstract / entry point for those with access, e.g. The Pawar 2023 source has an arXiv of 2311.10330, whereas below it is just an offline reference. ChrysGalley (talk) 11:17, 20 December 2025 (UTC)

Magic labeling

A (distance) magic labeling of a graph G is a bijection from the vertex set V(G) to the first |V(G)| such that the weight of every vertex is the same. The weight of a vertex is defined as the sum of the labels assigned to all vertices adjacent to it. If such a labeling exists and all vertex weights are equal to a positive integer k, then G is called magic graph and k is called a magic its constant.

A (distance) magic labeling was also called 1-vertex magic labeling, -labeling (Sigma-labeling)..[1] , neighborhood magic graphs, etc. A widely accepted terminology is (distance) magic labeling.

Formal Definition

A graph G is said to be distance magic if there exists a bijection f : V(G)→ {1,2,...,|V(G)|} and a positive integer k such that w(v)=k for all v V(G). The value w(v) is called the weight of the vertex v and is defined by where N(v) denotes the open neighborhood of v. Such a positive integer is called magic constant of a graph.

This definition gives rise to two basic questions:

1. Which graphs admit a distance magic labeling?

Determining whether a given graph is distance magic is a challenging problem. Although several partial results and characterizations are known for specific classes of graphs, no complete characterization of distance magic graphs is currently available [2] [3] [4] [5].

Which graphs are magic? This question is only partially answered so far. It is believed that for a given n only a fraction of all graphs of order n are magic[6] There is no general characterization of this graph class. All magic graphs of order up to 10 can be found here.[7]

Number of non-isomorphic distance magic graphs of order up to 12
number of vertices: n 3 4 5 6 7 8 9 10 11 12
number of non-isomorphic distance magic graphs 1 1 1 1 3 6 5 5 74 1160

2. Which natural numbers can occur as magic constants?

It is known that all natural numbers except 1,2,4,6,8,12, and 16 are magic constants [7]. Thus there is a sequence of magic constants 3, 5, 7, 9, 10, 11, 13, 14, 15, 17, 18, 19, 20, ...[8]

References

  1. ^ Vilfred, V. (1994). Σ-Labelled Graphs and Circulant Graphs. Ph.D. thesis, University of Kerala, Trivandrum, India.
  2. ^ Miller, Mirka; Rodger, Chris; Simanjuntak, Rinovia (2003). "Distance magic labelings of graphs". Australasian Journal of Combinatorics. 28: 305–315. ISSN 1034-4942. MR 1999203.
  3. ^ Sugeng, K. A.; Froncek, D.; Miller, M.; Ryan, J.; Walker, J. (2009). "On distance magic labeling of graphs". Journal of Combinatorial Mathematics and Combinatorial Computing. 71: 39–48. ISSN 0835-3026. MR 2568905.
  4. ^ Kovar, Petr; Froncek, Dalibor; Kovarova, Tereza (2012). "A note on 4-regular distance magic graphs". Australasian Journal of Combinatorics. 54: 127–132. ISSN 1034-4942. MR 3013245.
  5. ^ Cichacz, Sylwia (2014). "Distance magic graphs G\times C_n". Discrete Applied Mathematics. 177: 80–87. doi:10.1016/j.dam.2014.05.044. ISSN 0166-218X. MR 3249793.
  6. ^ Yasin, F.; Simanjuntak, R. (2015). "A heuristic for distance magic labeling". Procedia Computer Science 74, 100–104.
  7. ^ a b Ravindra Pawar; Tarkeshwar Singh, Himadri Mukherjee, Jay Bagga, (2024). "A complete characterization of magic constants arising from distance magic graphs". Journal of Combinatorial Mathematics and Combinatorial Computing 123, 287–302.
  8. ^ Ravindra Pawar. "Sequence of magic constants related to distance magic graphs". OEIS Foundation. Retrieved 2025-02-15.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.