Magic Coverings

Abstract

A simple graph $G=(V,E)$ admits an $H$-\emph{covering} if every edge in $E$ belongs to a subgraph of $G$ isomorphic to $H$. In this case, we say that $G$ is $H$-\emph{magic} if there is a total labeling $f:V\cup E\to \{1,2,\dots ,|V|+|E|\}$ such that for each subgraph $H^{\prime }=(V^{\prime },E^{\prime })$ of $G$ isomorphic to $H$,

$$\sum _{v\in V^{\prime }}f(v)+\sum _{e\in E^{\prime }}f(e)$$

is constant. When $f(V)=\{1,\dots ,|V|\}$, we say that $G$ is $H$-\emph{supermagic}.

We study $H$-magic graphs for several classes of connected graphs. We also provide constructions of infinite families of $H$-magic graphs for an arbitrary given graph $H$.