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
    0 references
    0 references
    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

    Identifiers