Graceful, Harmonious and Magic Type Labelings

Primarily for graduate students, this book has only the briefest introductory material. Ready understanding of bijections, equivalence relations, and other concepts used in proof but not introduced or defined is expected. Having stated the standard definitions and notations for finite graphs, the core concepts begin on page 15.

Loopless graphs with vertices labeled with distinct whole numbers having edges labeled with the absolute differences of adjacent vertices are graceful when those edge values enumerate the edges. Elaborating on this definition brings forth a taxonomy of graceful labelings and more, including magic labelings. Here “magic” is as in magic squares: a constant sum occurs for edges and adjacent vertices (edge-magic) or vertices and their incident edges (vertex-magic).

This is not merely a curated presentation of classified labelings. The book contains open problems, an unpublished result from Erdős on graceful graphs, and some applications, including to coding theory. A paper by Joseph A. Gallian referenced here is “A guide to the graph labeling zoo” (Discrete Applied Mathematics 49, 1994, 213-229). This slim, focused atlas is not only a delineation of species that can be met in the menagerie, but a sketch of what can still be found in the wild.

Tom Schulte is a software architect working in API management at SaaS ERP provide Plex Systems in Troy, Michigan.