Page 297 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 297
PHS AND GROUPS, GEOMETRIES AND GAP - G2G2 (MS-7)
(i) the eigenvalues of A are
α = b(n − 1) − k(k − 1) α2 = k − b − θ22, ..., αn = k − b − θn2;
b−a , b−a b−a
(ii) the eigenvalues of B are
β = a(n − 1) − k(k − 1) β2 = k − a − θ22, ..., βn = k − a − θn2.
a−b , a−b a−b
By Theorem above, a strongly Deza graph has at most three distinct absolute values of its
eigenvalues.
Theorem 2. Suppose G is a strongly Deza graph with parameters (n, k, b, a). Then
(i) G has at most five distinct eigenvalues.
(ii) If G has two distinct eigenvalues, then a = 0, b = k − 1 1, and G is a disjoint union
of cliques of order k + 1.
(iii) If G has three distinct eigenvalues, then G is a strongly regular graph with parameters
(n, k, λ, µ), where {λ, µ} = {a, b}, or G is disconnected and each component is a strongly
regular graph with parameters (v, k, b, b), or each component is a complete bipartite graph
Kk,k with k 2.
If G is a bipartite graph, then the halved graphs of G are two connected components of the
graph on the same vertex set, where two vertices are adjacent whenever they are at distance two
in G.
The next theorem gives a spectral characterization of strongly Deza graphs.
Theorem 3. Let G be a connected Deza graph with parameters (n, k, b, a), b > a, and it has at
most three distinct absolute values of its eigenvalues.
(i) If G is a non-bipartite graph, then G is a strongly Deza graph.
(ii) If G is a bipartite graph, then either G is a strongly Deza graph or its halved graphs are
strongly Deza graphs.
We also discuss some results on distance-regular strongly Deza graphs.
The main results of the talk are presented in [2].
The work of the speaker is supported by the Mathematical Center in Akademgorodok, the
agreement with Ministry of Science and High Education of the Russian Federation number
075-15-2019-1613.
References
[1] S. Akbari, A. H. Ghodrati, M. A. Hosseinzadeh, V. V. Kabanov, E. V. Konstantinova,
L. V. Shalaginov, Spectra of Deza graphs, Linear and Multilinear Algebra (2020).
https://doi.org/10.1080/03081087.2020.1723472
[2] S. Akbari, W. H. Haemers, M. A. Hosseinzadeh, V. V. Kabanov, E. V. Konstantinova,
L. Shalaginov, Spectra of strongly Deza graphs. https://arxiv.org/abs/2101.
06877
[3] A. Deza., M. Deza, The ridge graph of the metric polytope and some relatives. In:
Bisztriczky T., McMullen P., Schneider R., Weiss A.I. (eds) Polytopes: Abstract, Convex
and Computational. NATO ASI Series (Series C: Mathematical and Physical Sciences),
Vol. 440 (1994) 359–372, Springer, Dordrecht.
295
(i) the eigenvalues of A are
α = b(n − 1) − k(k − 1) α2 = k − b − θ22, ..., αn = k − b − θn2;
b−a , b−a b−a
(ii) the eigenvalues of B are
β = a(n − 1) − k(k − 1) β2 = k − a − θ22, ..., βn = k − a − θn2.
a−b , a−b a−b
By Theorem above, a strongly Deza graph has at most three distinct absolute values of its
eigenvalues.
Theorem 2. Suppose G is a strongly Deza graph with parameters (n, k, b, a). Then
(i) G has at most five distinct eigenvalues.
(ii) If G has two distinct eigenvalues, then a = 0, b = k − 1 1, and G is a disjoint union
of cliques of order k + 1.
(iii) If G has three distinct eigenvalues, then G is a strongly regular graph with parameters
(n, k, λ, µ), where {λ, µ} = {a, b}, or G is disconnected and each component is a strongly
regular graph with parameters (v, k, b, b), or each component is a complete bipartite graph
Kk,k with k 2.
If G is a bipartite graph, then the halved graphs of G are two connected components of the
graph on the same vertex set, where two vertices are adjacent whenever they are at distance two
in G.
The next theorem gives a spectral characterization of strongly Deza graphs.
Theorem 3. Let G be a connected Deza graph with parameters (n, k, b, a), b > a, and it has at
most three distinct absolute values of its eigenvalues.
(i) If G is a non-bipartite graph, then G is a strongly Deza graph.
(ii) If G is a bipartite graph, then either G is a strongly Deza graph or its halved graphs are
strongly Deza graphs.
We also discuss some results on distance-regular strongly Deza graphs.
The main results of the talk are presented in [2].
The work of the speaker is supported by the Mathematical Center in Akademgorodok, the
agreement with Ministry of Science and High Education of the Russian Federation number
075-15-2019-1613.
References
[1] S. Akbari, A. H. Ghodrati, M. A. Hosseinzadeh, V. V. Kabanov, E. V. Konstantinova,
L. V. Shalaginov, Spectra of Deza graphs, Linear and Multilinear Algebra (2020).
https://doi.org/10.1080/03081087.2020.1723472
[2] S. Akbari, W. H. Haemers, M. A. Hosseinzadeh, V. V. Kabanov, E. V. Konstantinova,
L. Shalaginov, Spectra of strongly Deza graphs. https://arxiv.org/abs/2101.
06877
[3] A. Deza., M. Deza, The ridge graph of the metric polytope and some relatives. In:
Bisztriczky T., McMullen P., Schneider R., Weiss A.I. (eds) Polytopes: Abstract, Convex
and Computational. NATO ASI Series (Series C: Mathematical and Physical Sciences),
Vol. 440 (1994) 359–372, Springer, Dordrecht.
295
