ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


P. Kovář, M. Kravčenko, A. Silber, M. Krbeček


Supermagic graphs with many different degrees


Discussiones Mathematicae Graph Theory

Received: 2018-11-21, Revised: 2019-04-08, Accepted: 2019-04-09,


Let $G=(V,E)$ be a graph with $n$ vertices and $e$ edges. A supermagic labeling of $G$ is a bijection $f$ from the set of edges $E$ to a set of consecutive integers $\{a, a+1,\dots,a+e-1\}$ such that for every vertex $v \in V$ the sum of labels of all adjacent edges equals the same constant $k$. This $k$ is called a magic constant of $f$, and $G$ is a supermagic graph.<br>The existence of supermagic labeling for certain classes of graphs has been the scope of many papers. For a comprehensive overview see Gallian's Dynamic survey of graph labeling in the Electronic Journal of Combinatorics. So far, regular or almost regular graphs have been studied. This is natural, since the same magic constant has to be achieved both at vertices of high degree as well as at vertices of low degree, while the labels are distinct consecutive integers.<br>The question of the existence of highly irregular supermagic graphs had remained open. In this paper we give a positive answer: the degree difference of a supermagic graph can be arbitrarily high. Moreover, we show that the composition $G[\overline{K}_n]$ is supermagic for every supermagic graph $G$ and odd $n$.


graph labeling, supermagic labeling, non-regular graphs