<abstract xmlns="http://www.w3.org/1999/xhtml">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.</abstract>

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.

Xor-Magic Graphs

Recreational Mathematics Magazine

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"Xor-Magic Graphs"}

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...

Xor-Magic Graphs

Published Online: Oct 11, 2019

Page range: 35 - 44

DOI: https://doi.org/10.2478/rmm-2019-0004

Keywords
cubic graph, regular graph, graph theory, combinatorics, linear algebra, binary, xor

© 2019 Jacob A. Siehler, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Xor-Magic Graphs

Published Online: Oct 11, 2019

Page range: 35 - 44

DOI: https://doi.org/10.2478/rmm-2019-0004

Keywordscubic graph, regular graph, graph theory, combinatorics, linear algebra, binary, xor

© 2019 Jacob A. Siehler, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Keywords
cubic graph, regular graph, graph theory, combinatorics, linear algebra, binary, xor