Integral graphs with unique patterns found from groups and recursive builds
Structural Characterizations and Algebraic Realizations of a Family of Regular Integral Graphs
Discrete Mathematics
Summary
Integral graphs have all their special numbers, called eigenvalues, as whole numbers, which is very rare. Most known integral graphs come from a certain kind called Cayley graphs, but the authors found a new way to build them using groups differently. They showed that each graph in their new family can be uniquely identified just by looking at these special numbers. They also found ways to make bigger integral graphs from smaller ones, and studied connections to special group-based graphs, even finding some that share these special numbers despite looking different.
What this means in practice
- •For network algorithm designers: Develop graph-based models whose structure can be uniquely determined from spectral data in communication or data networks.
- •For quantum computing engineers: Use uniquely characterized integral graphs in designing quantum state transfer networks where spectral properties matter.
Authors
Tapa Manna, Supriyo Dutta, Baby Bhattacharya
Abstract
All the eigenvalues of an integral graphs are integers. Integral graphs are extremely rare. They form an asymptotically vanishing fraction $2^{-Ω(n)}$ among all graphs on $n$ vertices. It makes the construction of a new family of integral graphs a challenging task. Also, most of the known infinite family of integral graphs rely on Cayley graphs over Abelian groups. In this article, we introduce a new family of integral graphs obtained from the groups. The construction of our graphs from groups is different from the construction of Cayley graphs. A spectral uniqueness theorem is established, which shows that each member of the infinite family is determined by its adjacency spectrum among all finite simple graphs. We also present recursive constructions that generates larger members of the family from smaller ones, providing a scalable class of integral graphs. Finally, we investigate algebraic realizations of these graphs as complements of Proper Prime Order Element Graphs of finite $2$-groups and obtain conditions characterizing such realizations. We also observe that the graphs obtained from different non-isomorphic groups have cospectral graphs.