Induced Graph Theorem on Magic Valuations

Hikoe Enomoto1, Kayo Masuda2, Tomoki Nakamigawa3
1Department of Mathematics, Faculty of Science and Technology Keio University Hiyoshi 3-14-1, Kohoku-ku, Yokohama, 223-8522, Japan
2Infrastructure Information Systems Division Oki Electric Industry Co.,Ltd. Shibaura 4-10-3, Minato-ku, Tokyo 108-8551, Japan
3Department of Mathematics, Faculty of Science and Technology Keio University Hiyoshi 3-14-1, Kohoku-ku, Yokohama 223-8522, Japan

Abstract

Let \(G\) be a graph. A bijection \(f\) from \(V(G) \cup E(G)\) to \(\{1,2,\ldots,|V(G)| + |E(G)|\}\) is called a magic valuation if \(f(u)+f(v)+f(uv)\) is constant for any edge \(uv\) in \(G\). A magic valuation \(f\) of \(G\) is called a supermagic valuation if \(f(V(G)) = \{1,2,\ldots,|V(G)|\}\). The following theorem is proved.For any graph \(H\), there exists a connected graph \(G\) so that \(G\) contains \(H\) as an induced subgraph and \(G\) has a supermagic valuation.