2022/11/08 by Rikio Ichishima, Ichishima, Rikio, S. C. López +5
Computer Science · Mathematics · #05C78 43A46 90C27 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2211.04029
openalex publication_date 2022/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G is called edge-magic if there exists a bijective function f:V(G) ∪ E(G)→ \1, 2, … , \vert V( G) \vert +\vert E( G) \vert \ such that f(u) + f(v) + f(uv) is a constant for each uv∈ E( G) . Also, G is said to be super edge-magic if f(V (G)) =\1, 2, … , \vert V( G) \vert \. Furthermore, the super edge-magic deficiency μs(G) of a graph G is defined to be either the smallest nonnegative integer n with the property that G ∪ nK1 is super edge-magic or + ∞ if there exists no such integer n. In this paper, we introduce the parameter l(n) as the minimum size of a graph G of order n for which all graphs of order n and size at least l(n) have μs ( G )=+∞ , and provide lower and upper bounds for l(G). Imran, Baig, and Feunovucíková established that for integers n with n≡ 0\pmod4, μs(Dn) ≤ 3n/2-1, where Dn is the cartesian product of the cycle Cn of order n and the complete graph K2 of order 2. We improve this bound by showing that μs(Dn) ≤ n+1 when n ≥ 4 is even. Enomoto, Lladó, Nakamigawa, and Ringel posed the conjecture that every nontrivial tree is super edge-magic. We propose a new approach to attak this conjecture. This approach may also help to resolve another labeling conjecture on trees by Graham and Sloane.