NUK - logo
E-resources
Full text
Peer reviewed Open access
  • Generalized Paley graphs eq...
    Podestá, Ricardo A.; Videla, Denis E.

    Linear & multilinear algebra, 02/2024, Volume: 72, Issue: 3
    Journal Article

    We consider generalized Paley graphs $ \Gamma (k,q) $ Γ ( k , q ) , generalized Paley sum graphs $ \Gamma ^+(k,q) $ Γ + ( k , q ) , and their corresponding complements $ \bar \Gamma (k,q) $ Γ ¯ ( k , q ) and $ \bar \Gamma ^+(k,q) $ Γ ¯ + ( k , q ) , for k = 3, 4. Denote by $ \Gamma =\Gamma ^*(k,q) $ Γ = Γ ∗ ( k , q ) either $ \Gamma (k,q) $ Γ ( k , q ) or $ \Gamma ^+(k,q) $ Γ + ( k , q ) . We compute the spectra of $ \Gamma (3,q) $ Γ ( 3 , q ) and $ \Gamma (4,q) $ Γ ( 4 , q ) and from them we obtain the spectra of $ \Gamma ^+(3,q) $ Γ + ( 3 , q ) and $ \Gamma ^+(4,q) $ Γ + ( 4 , q ) also. Then we show that, in the non-semiprimitive case, the spectrum of $ \Gamma (3,p^{3\ell }) $ Γ ( 3 , p 3 ℓ ) and $ \Gamma (4,p^{4\ell }) $ Γ ( 4 , p 4 ℓ ) with p prime can be recursively obtained, under certain arithmetic conditions, from the spectrum of the graphs $ \Gamma (3,p) $ Γ ( 3 , p ) and $ \Gamma (4,p) $ Γ ( 4 , p ) for any $ \ell \in \mathbb{N} $ ℓ ∈ N , respectively. Using the spectra of these graphs we give necessary and sufficient conditions on the spectrum of $ \Gamma ^*(k,q) $ Γ ∗ ( k , q ) such that $ \Gamma ^*(k,q) $ Γ ∗ ( k , q ) and $ \bar \Gamma ^*(k,q) $ Γ ¯ ∗ ( k , q ) are equienergetic for k = 3, 4. In a previous work we have classified all bipartite regular graphs $ \Gamma _{\rm bip} $ Γ bip and all strongly regular graphs $ \Gamma _{\rm srg} $ Γ srg which are complementary equienergetic, i.e. $ \{\Gamma _{\rm bip}, \bar {\Gamma }_{\rm bip}\} $ { Γ bip , Γ ¯ bip } and $ \{\Gamma _{\rm srg}, \bar {\Gamma }_{\rm srg}\} $ { Γ srg , Γ ¯ srg } are equienergetic pairs of graphs. Here we construct infinite pairs of equienergetic non-isospectral regular graphs $ \{\Gamma, \bar \Gamma \} $ { Γ , Γ ¯ } which are neither bipartite nor strongly regular.