1. bookVolume 6 (2019): Issue 11 (September 2019)
Journal Details
License
Format
Journal
eISSN
2182-1976
First Published
16 Apr 2016
Publication timeframe
2 times per year
Languages
English
access type Open Access

Xor-Magic Graphs

Published Online: 11 Oct 2019
Volume & Issue: Volume 6 (2019) - Issue 11 (September 2019)
Page range: 35 - 44
Journal Details
License
Format
Journal
eISSN
2182-1976
First Published
16 Apr 2016
Publication timeframe
2 times per year
Languages
English
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.

Keywords

[1] Brinkmann, G., Coolsaet, K., Goedgebeur, J., Mélot, H. “House of graphs: a database of interesting graphs”, Discrete Applied Mathematics, 161(1-2), 311–314, 2013.10.1016/j.dam.2012.07.018Search in Google Scholar

[2] Brinkmann, G., Goedgebeur, J., D McKay, B. “Generation of cubic graphs”. Discrete Mathematics and Theoretical Computer Science, 13(2), 69–79, 2011.10.46298/dmtcs.551Search in Google Scholar

[3] Conway, J., Norton, S., Ryba, A. “Frenicle’s 880 magic squares”, The Mathematics of Various Entertaining Subjects: Research in Games, Graphs, Counting, and Complexity, 2, 71, 2017.Search in Google Scholar

[4] Ekenta, O., Han Gil Jang, Siehler, J. “Slide-and-swap permutation groups”, Involve, a Journal of Mathematics, 7(1), 41–55, 2013.10.2140/involve.2014.7.41Search in Google Scholar

[5] N. J. A. Sloane. Online encyclopedia of integer sequences. http://oeis.org/A002851.Search in Google Scholar

[6] N. J. A. Sloane. Online encyclopedia of integer sequences. http://oeis.org/A032355.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo