Page 326 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 326
SPECTRAL GRAPH THEORY (MS-46)
Optimal Grid Drawings of Complete Multipartite Graphs and an Integer
Variant of the Algebraic Connectivity
Clemens Huemer, clemens.huemer@upc.edu
Universitat Politècnica de Catalunya, Spain
Coauthors: Ruy Fabila-Monroy, Carlos Hidalgo-Toscano, Dolores Lara, Dieter Mitsche
We use spectral graph theory to show how to draw the vertices of a complete multipartite graph
G on different points of a bounded d-dimensional integer grid, such that the sum of squared
distances between vertices of G is (i) minimized or (ii) maximized. For both problems we
provide a characterization of the solutions. For the particular case d = 1, our solution for (i)
also settles the minimum-2-sum problem for complete bipartite graphs; the minimum-2-sum
problem was defined by Juvan and Mohar in 1992. Weighted centroidal Voronoi tessellations
are the solution for (ii). Such drawings are related with Laplacian eigenvalues of graphs. This
motivates us to study which properties of the algebraic connectivity of graphs carry over to the
restricted setting of drawings of graphs with integer coordinates.
Strongly regular signed graphs and association schemes
Ivana Jovovic´, ivana@etf.rs
School of Electrical Engineering, University of Belgrade, Serbia
Coauthors: Tamara Koledin, Zoran Stanic´
We consider relations between strongly regular signed graphs and symmetric association schemes.
Our results include constructions of new examples of such signed graphs, relations between
their structure and spectra, and their classifications.
We also propose definitions of Johnson signed graphs and Hamming signed graphs that arise
from Johnson and Hamming schemes and act as the ‘signed’ counterparts to the well-known
Johnson and Hamming graphs. We compute the eigenvalues of these signed graphs and provide
necessary and sufficient conditions for their strong regularity. We also provide some results con-
cerning strongly regular signed graphs that naturally arise from Johnson and Hamming schemes
and have a comparatively small number of eigenvalues. Some constructions of strongly regular
Johnson and Hamming signed graphs with at most five eigenvalues are provided.
Classes of strongly regular signed graphs
Tamara Koledin, tamara@etf.bg.ac.rs
School of Electrical Engineering, University of Belgrade, Serbia
Coauthors: Ivana Jovovic´, Zoran Stanic´
We consider a concept of strong regularity defined for signed graphs – a generalization of strong
regularity of the unsigned ones. We say that the signed graph G˙ is strongly regular (for short,
G˙ is a SRSG) whenever it is regular, neither homogeneous complete nor totally disconnected,
and if its adjacency matrix AG˙ satisfies
AG2˙ = a + AG) − b − AG) + cAG + rI,
2 (AG˙ 2 (AG˙
324
Optimal Grid Drawings of Complete Multipartite Graphs and an Integer
Variant of the Algebraic Connectivity
Clemens Huemer, clemens.huemer@upc.edu
Universitat Politècnica de Catalunya, Spain
Coauthors: Ruy Fabila-Monroy, Carlos Hidalgo-Toscano, Dolores Lara, Dieter Mitsche
We use spectral graph theory to show how to draw the vertices of a complete multipartite graph
G on different points of a bounded d-dimensional integer grid, such that the sum of squared
distances between vertices of G is (i) minimized or (ii) maximized. For both problems we
provide a characterization of the solutions. For the particular case d = 1, our solution for (i)
also settles the minimum-2-sum problem for complete bipartite graphs; the minimum-2-sum
problem was defined by Juvan and Mohar in 1992. Weighted centroidal Voronoi tessellations
are the solution for (ii). Such drawings are related with Laplacian eigenvalues of graphs. This
motivates us to study which properties of the algebraic connectivity of graphs carry over to the
restricted setting of drawings of graphs with integer coordinates.
Strongly regular signed graphs and association schemes
Ivana Jovovic´, ivana@etf.rs
School of Electrical Engineering, University of Belgrade, Serbia
Coauthors: Tamara Koledin, Zoran Stanic´
We consider relations between strongly regular signed graphs and symmetric association schemes.
Our results include constructions of new examples of such signed graphs, relations between
their structure and spectra, and their classifications.
We also propose definitions of Johnson signed graphs and Hamming signed graphs that arise
from Johnson and Hamming schemes and act as the ‘signed’ counterparts to the well-known
Johnson and Hamming graphs. We compute the eigenvalues of these signed graphs and provide
necessary and sufficient conditions for their strong regularity. We also provide some results con-
cerning strongly regular signed graphs that naturally arise from Johnson and Hamming schemes
and have a comparatively small number of eigenvalues. Some constructions of strongly regular
Johnson and Hamming signed graphs with at most five eigenvalues are provided.
Classes of strongly regular signed graphs
Tamara Koledin, tamara@etf.bg.ac.rs
School of Electrical Engineering, University of Belgrade, Serbia
Coauthors: Ivana Jovovic´, Zoran Stanic´
We consider a concept of strong regularity defined for signed graphs – a generalization of strong
regularity of the unsigned ones. We say that the signed graph G˙ is strongly regular (for short,
G˙ is a SRSG) whenever it is regular, neither homogeneous complete nor totally disconnected,
and if its adjacency matrix AG˙ satisfies
AG2˙ = a + AG) − b − AG) + cAG + rI,
2 (AG˙ 2 (AG˙
324
