Integral Circulant Graphs and So’s Conjecture

Year 2024, Volume: 16 Issue: 1, 169 - 176, 30.06.2024

Ercan Altınışık , Sümeyye Büşra Aydın

https://doi.org/10.47000/tjmcs.1461910

Abstract

An integral circulant graph is a circulant graph whose adjacency matrix has only integer eigenvalues. It was conjectured by W. So that there are exactly $2^{\tau(n) - 1}$ non-isospectral integral circulant graphs of order $n$, where $\tau ( n )$ is the number of divisors of $n$. However, the conjecture remains unproven. In this paper, we present the fundamental concepts and results on the conjecture. We obtain the relation between two characterizations of integral circulant graphs given by W. So and by W. Klotz and T. Sander . Finally,we calculate the eigenvalues of the integral circulant graph $G$ if $S(G) = G_{n}(d)$ for any $d \in D $. Here $G_{n}(d)$ is the set of all integers less than $n$ that have the same greatest common divisor $d$ with $n$.

Keywords

circulant graph, integral graph, eigenvalue, spectrum, So’s conjecture

References

• Biggs, N., Algebraic Graph Theory, Cambridge University Press, London, 1993.
• Klotz, W., Sander, T., Some properties of unitary Cayley graphs, The Electronic Journal of Combinatorics, (2007).
• Mönius, K., So, W., How many non-isospectral integral circulant graphs are there?, Australasian Journal of Combinatorics, 86(2023), 320– 335.
• Sander, J.W., Sander T., On So’s conjecture for integral circulant graphs, Applicable Analysis and Discrete Mathematics, (2015), 59–72.
• So, W., Integral circulant graphs, Discrete Mathematics, 306(2006), 153–158.