Spectral and combinatorial properties of some algebraically defined graphs
type: Item
instance of: scholarly article
title: Spectral and combinatorial properties of some algebraically defined graphs
zbMATH Open document ID: 1410.05121
author: Sebastian Cioaba
author: Felix Lazebnik
author: Shuying Sun
published in: The Electronic Journal of Combinatorics
publication date: 2019-03-05T00:00:00Z
full work available at URL: https://arxiv.org/abs/1708.07597
full work available at URL: v25i4p60
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.
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 7032066
zbMATH Keywords: graph spectra
zbMATH Keywords: expanders
zbMATH Keywords: algebraically defined graphs
MaRDI profile type: MaRDI publication profile
arXiv ID: 1708.07597
cites work: \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
cites work: Eigenvalues and expanders
cites work: Spectra of Cayley graphs
cites work: Q4398864
cites work: Spectra of graphs
cites work: Linearized Wenger graphs
cites work: On the spectrum of Wenger graphs
cites work: Q4787524
cites work: Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
cites work: Expander graphs and their applications
cites work: Q3102220
cites work: Q5354851
cites work: New examples of graphs without small cycles and of large size
cites work: Explicit construction of graphs with an arbitrary large girth and of large size
cites work: General properties of some families of graphs defined by systems of equations
cites work: Spectra of graphs with transitive groups
cites work: Isoperimetric numbers of graphs
cites work: The eigenvalues of the graphs \(D(4,q)\)
cites work: On the second eigenvalue of a graph
cites work: A note on the spectrum of linearized Wenger graphs
Recommended article: Some algebraic properties of a class of integral graphs determined by their spectrum
Recommended article: Some properties of the spectrum of graphs
Recommended article: On the spectral characterizations of graphs
Recommended article: Q3222218
Recommended article: Spectral characterizations of almost complete graphs
Recommended article: Graphs determined by their \(A_\alpha\)-spectra
Recommended article: Some results on graph spectra
Recommended article: On the \(A_\alpha\)-spectra of graphs
Recommended article: Q4656880
Recommended article: Combinatorial and spectral properties of König-Egerváry graphs
description: scientific article