Article Details

Version for online viewing      Version for printing

Xor-Magic Graphs
Jacob A. Siehler
A connected graph on 2n vertices is defined to be xor-magic if the vertices can be labeled with distinct n-bit binary numbers in such a way that the label at each vertex is equal to the bitwise xor of the labels on the adjacent vertices.  We show that there is at least one 3-regular xor-magic graph on 2n vertices for every n≥2. We classify the 3-regular xor-magic graphs on 8 and 16 vertices, and give multiple examples of 3-regular xor-magic graphs on 32 vertices, including the well-known Dyck graph.
cubic graph, regular graph, graph theory, combinatorics, linear algebra, binary, xor
Published: 2019/10/14
Author Details
Jacob A. Siehler
Gustavus Adolphus College

     About us | Editorial Board | To the authors | Contact us