Steinhaus Graphs and Its Application in Cryptography

Abstract

The concept of an adjacency matrix in graph theory stems from the inherent structure of a graph. Mullunzzo derived a graph from a Steinhaus matrix, characterized by being $(0,1)$-symmetric with a zero diagonal, by extending a Steinhaus triangle into an adjacency matrix. The Steinhaus graph, a representation of this process, behaves akin to an XOR logical gate, lending itself to applications in cryptography alongside graph theory. This paper delves into the notion of a Steinhaus complement within the realm of Steinhaus graphs, introducing the concept of Steinhaus self-complementary graphs. Exploring vertex set partitions of Steinhaus graphs, particular focus is placed on identifying 2--partitions that yield the Steinhaus graph as their 2-complement. Utilizing the notion of a 2-self--omplement of a graph, the characterization of Steinhaus self-complementary graphs is elucidated. The paper also outlines insights from Steinhaus graphs that contribute to the advancement of symmetric cryptography.