Bounds on the Size of Super Edge-Magic Graphs Depending on the Girth

Abstract

Let $G=(V,E)$ be a graph of order $p$ and size $q$. It is known that if $G$ is a super edge-magic graph, then $q\le 2p–3$. Furthermore, if $G$ is super edge-magic and $q=2p–3$, then the girth of $G$ is $3$. Additionally, if the girth of $G$ is at least $4$ and $G$ is super edge-magic, then $q\le 2p–5$. In this paper, we demonstrate that there are infinitely many graphs that are super edge-magic, have girth $5$, and $q=2p–5$. Hence, we conclude that for super edge-magic graphs of girths $4$ and $5$, the size is upper bounded by twice the order of the graph minus $5$, and this bound is tight.