On the spectral Ádám property for circulant graphs
type: Item
instance of: scholarly article
title: On the spectral Ádám property for circulant graphs
zbMATH Open document ID: 1035.05059
DOI: 10.1016/S0012-365X(01)00374-0
author: Bernard Mans
author: Francesco Pappalardi
author: Igor E. Shparlinski
published in: Discrete Mathematics
publication date: 2002-08-29T00:00:00Z
review text: This paper extends the class of graphs having the Ádám property and having the (even more general) spectral Ádám property. The methods employed in this paper are based on a combination of spectral techniques and deep results of algebraic number theory. A {circulant graph} \(G\) is a graph whose adjacency matrix \(A\) is a circulant, that is, the \(i\)th row of \(A\) is the cyclic shift of the first row by \(i-1\). If \(S\subseteq Z_n\) is the set of positions of nonzero entries of the first row of \(A\), then we write \(G=\langle S\rangle_n\). Two sets \(S\) and \(T\) are {proportional} if \(S=lT\) for some integer \(l\) where \(\gcd(n,l)=1\) and multiplication is taken over \(Z_n\). A set \(S\subseteq Z_n\) has the {Ádám property} if the isomorphism \(\langle S\rangle_n\simeq \langle T\rangle_n\) implies the proportionality \(S\sim T\). A more general form of the Ádám property is investigated in this paper. The spectrum \(\text{ Spec}\;G\) of a graph is the set of eigenvalues with multiplicities of its adjacency matrix. A set \(S\subseteq Z_n\) has the {spectral Ádám property} if the isospectrality \(\text{ Spec}\;\langle S\rangle_n=\text{ Spec}\;\langle T\rangle_n\) implies the proportionality \(S\sim T\). The authors show that any set \(S=\{\pm a,\pm b\}\subseteq Z_n\) with \(\gcd(a,b,n)=1\) satisfies the spectral Ádám property. It is also shown that for any fixed \(m\) the probability that a random \(m\)-element set \(S\subseteq Z_n\) does not have the spectral Ádám property is \(O(n^{-1})\).
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1792466
zbMATH Keywords: isomorphism
reviewed by: Robert R. Molina
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00374-0
OpenAlex ID: W2134596794
description: scientific article; zbMATH DE number 1792466