Title |

Xor-Magic Graphs |

Authors |

Jacob A. Siehler |

Abstract |

A connected graph on 2 ^{n} 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 2^{n} 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 |

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

Milestones |

Published: 2019/10/14 |

Author Details |

Jacob A. Siehler jsiehler@gustavus.edu Gustavus Adolphus College |