2023/06/28 by Yukio Takahashi, Takahashi, Yukio, Francesc A. Muntaner-Batle +3
Computer Science · #05C78 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2306.15986
openalex publication_date 2023/06/28 · 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 (called the valence of f) for each uv∈ E( G) . If f(V (G)) =\1, 2, … , \vert V( G) \vert \, then G is called a super edge-magic graph. A stronger version of edge-magic and super edge-magic graphs appeared when the concepts of perfect edge-magic and perfect super edge-magic graphs were introduced. 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. On the other hand, the edge-magic deficiency μ(G) of a graph G is the smallest nonnegative integer n for which G∪ nK1 is edge-magic, being μ(G) always finite. In this paper, the concepts of (super) edge-magic deficiency are generalized using the concepts of perfect (super) edge-magic graphs. This naturally leads to the study of the valences of edge-magic and super edge-magic labelings. We present some general results in this direction and study the perfect (super) edge-magic deficiency of the star K1,n.