On the Construction of Xor-Magic Graphs

Abstract

A simple connected graph of order 2nis defined as a xor-magic graph of power n if its vertices can be labeled with vectors from Fn2 in a one-to-one manner such that the sum of labels in each closed neighborhood set of vertices equals zero. In this paper, we introduce a method called the self-switching operation, which, when properly applied to an odd xor-magic graph of power n, generates a xor-magic graph of power n + 1. We demonstrate the existence of a proper self-switching operation for any given odd xor-magic graph and provide a characterization of the cut space of a connected graph in the process. We also observe that the Dyck graph can be obtained from the complete graph of order 4 by applying three successive self-switching operations. Additionally, we investigate various graph products, including Cartesian, tensor, strong, lexicographical, and modular products. We observe that these products allow us to generate xor-magic graphs by selecting appropriate factor graphs. Notably, we discover that a modular product of graphs is always a xor-magic graph when the orders of its factors are powers of 2 (except for 2 itself). In the process, we realize that the Clebsch graph is the modular product of the cycle graph and the empty graph, each of order 4. By combining the self-switching operation with the modular product, we establish the existence of k-regular xor-magic graphs of power n for all n >= 2 and for all k is an element of {3, 5, 7, ... , 2n-5}boolean OR{2n-1}. We also prove that there is no (2n-3)-regular xor-magic graph of power n. Lastly, we introduce two more methods to produce xor-magic graphs. One method utilizes Cayley graphs and the other utilizes linear algebra. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.