Spectral and combinatorial properties of some algebraically defined graphs

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

algebraically defined graphs expanders graph spectra

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Let

k g e 3

be an integer,

q

be a prime power, and

m a t h b b F_{q}

denote the field of

q

elements. Let

f_{i}, g_{i} i n m a t h b b F_{q} [X]

,

3 l e i l e k

, such that

g_{i} (- X) = -, g_{i} (X)

. We define a graph

S (k, q) = S (k, q; f_{3}, g_{3}, c d o t s, f_{k}, g_{k})

as a graph with the vertex set

m a t h b b F_{q}^{k}

and edges defined as follows: vertices

a = (a_{1}, a_{2}, l d o t s, a_{k})

and

b = (b_{1}, b_{2}, l d o t s, b_{k})

are adjacent if

a_{1} e b_{1}

and the following

k - 2

relations on their components hold:

b_i-a_i = g_i(b_1-a_1)f_iBigl(frac{b_2-a_2}{b_1-a_1}Bigr);,quad 3le ile k.

We show that graphs

S (k, q)

generalize several recently studied examples of regular expanders and can provide many new such examples.

Review text

Summary: Let \(k\geq 3\) be an integer, \(q\) be a prime power, and \(\mathbb{F}_q\) denote the field of \(q\) elements. Let \(f_i, g_i\in\mathbb{F}_q[X]\), \(3\leq i\leq k\), such that \(g_i(-X) = -\, g_i(X)\). We define a graph \(S(k,q) = S(k,q;f_3,g_3,\dots,f_k,g_k)\) as a graph with the vertex set \(\mathbb{F}_q^k\) and edges defined as follows: vertices \(a = (a_1,a_2,\dots,a_k)\) and \(b = (b_1,b_2,\dots,b_k)\) are adjacent if \(a_1\neq b_1\) and the following \(k-2\) relations on their components hold: \[ b_i-a_i = g_i(b_1-a_1)f_i\bigg(\frac{b_{2}-a_{2}}{b_{1}-a_{1}}\bigg),\quad 3\leq i\leq k. \] We show that the graphs \(S(k,q)\) generalize several recently studied examples of regular expanders and can provide many new such examples.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Spectral and combinatorial properties of some algebraically defined graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q668032)