You are here

Magic Graphs

W. D. Wallis
Publication Date: 
Number of Pages: 
[Reviewed by
Fernando Q. Gouvêa
, on

This monograph deals with a particular class of graph labeling problems. Given a graph, the goal is to assign numbers to all edges and vertices of the graph in such a way as to satisfy certain constraints. In an "edge-magic total labeling," the constraint is that the sum of the numbers attached to each edge and its vertices be the same for all edges. In a "vertex-magic total labeling", we focus instead on each vertex, and require that the sum of the number attached to the vertex and to all the edges incident on it be constant (as a function of the vertex). Finally, a "totally magic labeling" is one that satisfies both constraints. Wallis brings together what is known about these problems, organizesthe results, and attempts to smooth out the contradictory notational conventions found in the literature.

The author's goal is to provide quick access to a live research area in which students can get a feel for what mathematical research is like. To further this goal, he includes several research problems (so marked) in addition to exercises. Two appendices give solutions to the exercises and notes on the research problems.

The book should be accessible to advanced undergraduates or beginning graduate students. It might serve as inspiration for an REU program or as a source for senior undergraduate research projects, particularly if supervised by a mathematician who is truly "up" on what is going on in this field.

Fernando Q. Gouvêa is professor of mathematics at Colby College in Waterville, ME.


Preface * List of Figures * 1. Preliminaries * 1.1 Magic * 1.2 Graphs * 1.3 Labelings * 1.4 Magic Labeling * 1.5 Some Applications of Magic Labelings * 2. Edge-Magic Total Labelings * 2.1 Basic Ideas * 2.2 Graphs with No Edge-Magic Total Labelings * 2.3 Cliques and Complete Graphs * 2.4 Cycles * 2.5 Complete Bipartite Graphs * 2.6 Wheels * 2.7 Trees * 2.8 Disconnected Graphs * 2.9 Strong Edge-Magic Total Labelings * 2.10 Edge-Magic Injections * 3. Vertex-Magic Total Labelings * 3.1 Basic Ideas * 3.2 Regular Graphs * 3.3 Cycles and Paths * 3.4 Vertex-Magic Total Labelings of Wheels * 3.5 Vertex-Magic Total Labelings of Complete Bipartite Graphs * 3.6 Graphs with Vertices of Degree One * 3.7 The Complete Graphs * 3.8 Disconnected Graphs * 3.9 Vertex-Magic Injections * 4. Totally Magic Labelings * 4.1 Basic Ideas * 4.2 Isolates and Stars * 4.3 Forbidden Configurations * 4.4 Unions of Triangles * 4.5 Small Graphs * 4.6 Totally Magic Injections * Notes on the Research Problems * Bibliography * Solutions to Selected Exercises * Index