Zero-sum magic labelings and null sets of regular graphs

Saieed Akbari¹ ; Farhad Rahmati² ; Sanaz Zare²

¹Sharif University of Technology
²Amirkabir University of Technology

The electronic journal of combinatorics, Tome 21 (2014) no. 2

Résumé

For every $h\in \mathbb{N}$, a graph $G$ with the vertex set $V(G)$ and the edge set $E(G)$ is said to be $h$-magic if there exists a labeling $l : E(G) \rightarrow\mathbb{Z}_h \setminus \{0\}$ such that the induced vertex labeling $s : V (G) \rightarrow \mathbb{Z}_h$, defined by $s(v) =\sum_{uv \in E(G)} l(uv)$ is a constant map. When this constant is zero, we say that $G$ admits a zero-sum $h$-magic labeling. The null set of a graph $G$, denoted by $N(G)$, is the set of all natural numbers $h \in \mathbb{ N} $ such that $G$ admits a zero-sum $h$-magic labeling. In 2012, the null sets of 3-regular graphs were determined. In this paper we show that if $G$ is an $r$-regular graph, then for even $r$ ($r > 2$), $N(G)=\mathbb{N}$ and for odd $r$ ($r\neq5$), $\mathbb{N} \setminus \{2,4\}\subseteq N(G)$. Moreover, we prove that if $r$ is odd and $G$ is a $2$-edge connected $r$-regular graph ($r\neq 5$), then $ N(G)=\mathbb{N} \setminus \{2\}$. Also, we show that if $G$ is a $2$-edge connected bipartite graph, then $\mathbb{N} \setminus \{2,3,4,5\}\subseteq N(G)$.

Détail

DOI : 10.37236/3654

Classification : 05C78
Mots-clés : magic labeling, null set, zero-sum flows, regular graph, bipartite graph