On the spectral Ádám property for circulant graphs (Q1613548)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the spectral Ádám property for circulant graphs |
scientific article |
Statements
On the spectral Ádám property for circulant graphs (English)
0 references
29 August 2002
0 references
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})\).
0 references
isomorphism
0 references