Page 293 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 293
GRAPHS AND GROUPS, GEOMETRIES AND GAP - G2G2 (MS-7)
References
[1] A. Blokhuis, On subsets of GF (q2) with square differences. Indag. Math. 46 (1984) 369–
372.
[2] R. D. Baker, G. L. Ebert, J. Hemmeter, A. J. Woldar, Maximal cliques in the Paley graph
of square order. J. Statist. Plann. Inference 56 (1996) 33–38.
[3] S. V. Goryainov, V. V. Kabanov, L. V. Shalaginov, A. A. Valyuzhenich, On eigenfunctions
and maximal cliques of Paley graphs of square order. Finite Fields and Their Applications
52 (2018) 361–369.
[4] S. V. Goryainov, A. V. Masley, L. V. Shalaginov, On a correspondence between maximal
cliques in Paley graphs of square order. arXiv:2102.03822 (2021).
Strongly regular graphs satisfying the 4-vertex condition
Ferdinand Ihringer, Ferdinand.Ihringer@gmail.com
Universiteit Gent, Belgium
Coauthors: Andries E. Brouwer, William M. Kantor
A graph Γ satisfies the t-vertex condition, when for all triples (T, x0, y0) of a t-vertex graph T
with two distinct distinguished vertices x0, y0, and all pairs of distinct vertices x, y of Γ, where
x ∼ y if and only if x0 ∼ y0, the number n(x, y) of isomorphic copies of T in Γ, where the
isomorphism maps x0 to x and y0 to y, does not depend on the choice of the pair x, y. A graph
satisfies the 3-vertex condition if and only if it is strongly regular. A graph of order v satisfies
the v-vertex condition if and only if it is rank 3. There are not many graphs known which satisfy
the 4-vertex condition. We discuss several new families of such graphs related to polar spaces.
One of our constructions is prolific and shows that the number of graphs satisfying the 4-vertex
condition growths hyperexponentially in the number of vertices.
Eigenfunctions of the Star graphs for all non-zero eigenvalues
Vladislav V. Kabanov, vvk@imm.uran.ru
Krasovskii Institute of Mathematics and Mechanics, Russian Federation
Coauthors: Leonid Shalaginov, Elena V. Konstantinova, Alexandr Valyuzhenich
Let G be a finite group and S be a subset of G which does not contain the identity element
and is closed under inversion. The Cayley graph Cay(G, S) is a graph with the vertex set G in
which two vertices x, y are adjacent if and only if xy−1 ∈ S. For Ω = {1, . . . , n}, n 2, we
consider the symmetric group SymΩ and put S = {(1 i) | i ∈ {2, . . . , n}}. The Star graph
Sn = Cay(SymΩ, S) is the Cayley graph over the symmetric group SymΩ with the generating
set S.
A function f : V (Γ) → R is called an eigenfunction of a graph Γ corresponding to an
eigenvalue θ if f ≡ 0 and the equality
θ · f (x) = f (y) (1)
y∈N (x)
291
References
[1] A. Blokhuis, On subsets of GF (q2) with square differences. Indag. Math. 46 (1984) 369–
372.
[2] R. D. Baker, G. L. Ebert, J. Hemmeter, A. J. Woldar, Maximal cliques in the Paley graph
of square order. J. Statist. Plann. Inference 56 (1996) 33–38.
[3] S. V. Goryainov, V. V. Kabanov, L. V. Shalaginov, A. A. Valyuzhenich, On eigenfunctions
and maximal cliques of Paley graphs of square order. Finite Fields and Their Applications
52 (2018) 361–369.
[4] S. V. Goryainov, A. V. Masley, L. V. Shalaginov, On a correspondence between maximal
cliques in Paley graphs of square order. arXiv:2102.03822 (2021).
Strongly regular graphs satisfying the 4-vertex condition
Ferdinand Ihringer, Ferdinand.Ihringer@gmail.com
Universiteit Gent, Belgium
Coauthors: Andries E. Brouwer, William M. Kantor
A graph Γ satisfies the t-vertex condition, when for all triples (T, x0, y0) of a t-vertex graph T
with two distinct distinguished vertices x0, y0, and all pairs of distinct vertices x, y of Γ, where
x ∼ y if and only if x0 ∼ y0, the number n(x, y) of isomorphic copies of T in Γ, where the
isomorphism maps x0 to x and y0 to y, does not depend on the choice of the pair x, y. A graph
satisfies the 3-vertex condition if and only if it is strongly regular. A graph of order v satisfies
the v-vertex condition if and only if it is rank 3. There are not many graphs known which satisfy
the 4-vertex condition. We discuss several new families of such graphs related to polar spaces.
One of our constructions is prolific and shows that the number of graphs satisfying the 4-vertex
condition growths hyperexponentially in the number of vertices.
Eigenfunctions of the Star graphs for all non-zero eigenvalues
Vladislav V. Kabanov, vvk@imm.uran.ru
Krasovskii Institute of Mathematics and Mechanics, Russian Federation
Coauthors: Leonid Shalaginov, Elena V. Konstantinova, Alexandr Valyuzhenich
Let G be a finite group and S be a subset of G which does not contain the identity element
and is closed under inversion. The Cayley graph Cay(G, S) is a graph with the vertex set G in
which two vertices x, y are adjacent if and only if xy−1 ∈ S. For Ω = {1, . . . , n}, n 2, we
consider the symmetric group SymΩ and put S = {(1 i) | i ∈ {2, . . . , n}}. The Star graph
Sn = Cay(SymΩ, S) is the Cayley graph over the symmetric group SymΩ with the generating
set S.
A function f : V (Γ) → R is called an eigenfunction of a graph Γ corresponding to an
eigenvalue θ if f ≡ 0 and the equality
θ · f (x) = f (y) (1)
y∈N (x)
291
