Totally Magic Injections of Graphs

Abstract

For a simple graph $G$, consider an injection $\mu :V\cup E\to \mathbb{N}$. If for every vertex $x\in V$ we have $\mu (x)+\sum _{y\sim x}\mu (xy)=h$, and for every edge $xy\in E(G)$ we have $\mu (x)+\mu (xy)+\mu (y)=k$, for some constants $h$ and $k$, then $\mu$ is a totally magic injection (TMI) of $G$. Also, $m_t(G)$ is the smallest number in $\mathbb{N}$ such that there is a TMI $\mu :V\cup E\to \{1,2,\dots ,m_t(G)\}$. Here we study TMIs and the number $m_t(G)$ for certain $G$. One theorem, the Star Theorem, is useful for eliminating many classes of well-known graphs that could have a TMI. For most $n$ and $n_j$, the following graphs do not have a TMI: every non-star tree, $P_n$, $C_n$, $W_n$, $K_n$, and $K_{n_1,n_2,\dots ,n_p}$. We determine $m_t(F)$ for every forest $F$ that has a TMI, and $m_t(G)$ for every graph $G$ with $\le 6$ vertices that has a TMI.