This is a local page for the invited Minisymposium on "Distance matrices
of graphs", at the 2022 meeting of the
International Linear
Algebra Society (ILAS). The Minisymposium takes place on
June 21 (Tue) and 23 (Thu).
The organizers are: Projesh Nath Choudhury and Apoorva Khare.
For information on hotels, and registration,
click on the ILAS 2022 logo at the top of this page.
Distance matrices associated to graphs have been explored intensively
in the literature for several decades now, both from an algebraic and a
spectral viewpoint. They have connections to graph embeddings,
communications networks, and quantum chemistry among other areas. This
minisymposium will bring together researchers working on distance
matrices from a variety of perspectives, and discuss modern approaches
and recent results.
Speakers


Abstract.
Graham and Lovász conjectured in 1978 that the sequence of
normalized coefficients of the distance characteristic polynomial of a
tree is unimodal with the maximum value occurring at $\lfloor \frac{n}{2}
\rfloor$ for a tree $T$ of order $n$. We extend this old conjecture to
block graphs. In particular, we prove the unimodality part and we
establish the peak for several extremal cases of block graphs.
This is joint work with B. Brimkov, S. Hayat, A. Khramova and J. Koolen.


Abstract.
Given a finite simple connected graph $G=(V,E)$ (or even a finite metric
space), we introduce a novel invariant which we call its
blowuppolynomial $p_G(n_v : v \in V)$. To do so, we compute the
determinant of the distance matrix of the graph blowup, obtained by
taking $n_v$ copies of the vertex $v$, and remove an exponential factor.
First: we show that as a function of the sizes $n_v$, $p_G$ is a
polynomial, is multiaffine, and is realstable. Second: we show that the
multivariate polynomial $p_G$ fully recovers $G$. Third: we obtain a
novel characterization of the complete multipartite graphs, as precisely
those whose "homogenized" blowuppolynomials are Lorentzian/strongly
Rayleigh. (Joint with Apoorva Khare.) 

Abstract.
Distance ideals of graphs generalize, among other graph parameters, the
spectrum and the Smith normal form (SNF) of distance and distance
Laplacian matrices. In particular, they allow us to introduce the notion
of codeterminantal graphs, which generalize the concepts of cospectral
and coinvariant graphs. We show computational results on codeterminantal
graphs up to 9 vertices. Although the spectrum of several graph matrices
has been widely used to determine graphs, the computational results
suggest that the SNF of the distance Laplacian matrix seems to perform
better for determining graphs. Finally, we show that complete graphs and
star graphs are determined by the SNF of its distance Laplacian
matrix.
This is joint work with Aida Abiad (Eindhoven University of Technology
and Ghent University), Kristin Heysse (Macalester College), Libby Taylor
(Stanford University) and Marcos C. Vargas (Banco de México).


Abstract.
The moment of a force $\textbf{F}$ applied to a point particle having
distance $\textbf{d}$ from a fixed fulcrum is the cross product
$\textbf{d}\times \textbf{F}$. We consider two graphtheoretic versions
of this notion, of different nature: Given a rooted tree $T$, its
combinatorial moment $\mu$ is given by the sum over each vertex
$v$ of the distance of $v$ from the root times the degree of $v;$ its
spectral moment $\rho$ is the largest eigenvalue of a square
matrix encoding the "common distance" from the root of pairs of vertices
in $T$. The features of both these parameters resemble those of their
physical counterpart. Therefore, they share a similar behaviour with
respect to elementary constructions on trees. This allows us to show that
$\mu$ is essentially an upper bound for $\rho$, and the ratio $\mu /\rho$
is at most linear in the order of $T$; specific classes of trees having a
fractal structure allow to conclude that $\mu /\rho$ is in fact unbounded
in general.
Interestingly, both $\mu$ and $\rho$ are closely linked to connectivity
notions for graphs – Kemeny's constant $\kappa$ and algebraic
connectivity $\alpha$, respectively. As a consequence, the quantitative
comparison between the two moments promises to shed some light on the
still shadowy relation between $\kappa$ and $\alpha$.


Abstract.
In the last ten years, variants of the distance matrix of a graph, such
as the distance Laplacian, the distance signless Laplacian, and the
normalized distance Laplacian matrix of a graph, have been studied. This
talk compares and contrasts techniques and results for these four
variants of distance matrices. New results are obtained by crossapplying
techniques from one variant of the distance matrix to another are
presented.
This is joint work with Carolyn Reinhart (Swarthmore).


Abstract.
A directed graph, or digraph, is a graph in which edges are replaced by
directional arcs. While the distance matrix and its variants are
symmetric matrices when defined on graphs, these matrices are not
necessarily symmetric on digraphs. Thus, some of the techniques used in
the graph case no longer apply. This talk will discuss techniques used to
study distance matrices for digraphs and some results they have yielded.
New results regarding cospectrality for the distance matrix of digraphs
will also be presented.
This is joint work with Leslie Hogben (Iowa State University and AIM).


Abstract.
Let $T$ be a tree with vertex set $V(T) = \{ 1, 2, \dots, n\}$. The
Steiner distance of $S \subseteq V(T)$ of vertices of $T$ is defined to
be the number of edges in a smallest connected subtree of $T$ that contains
all the vertices of $S$. The $k$Steiner distance matrix
$\mathfrak{D}_k(T)$ of $T$ is an $\binom{n}{k} \times \binom{n}{k}$
matrix whose rows and columns are indexed by subsets of vertices of size
$k$. The entry in the row indexed by $P$ and column indexed by $Q$ is
equal to Steiner distance of $P \cup Q$. When $k=1$, it is easy to see
that we have $\mathfrak{D}_1(T)=D(T)$, the distance matrix of $T$ which
is a well studied matrix. In this work, we consider the next case, that
is when $k=2$. We show that rank$(\mathfrak{D}_2(T))=2np1$, where $p$
is the number of pendant vertices (or leaves) in $T$. We construct a
basis $\mathfrak{B}$ for the row space of $\mathfrak{D}_2(T)$ and obtain
a formula for the inverse of the nonsingular square submatrix
$\mathfrak{D} = \mathfrak{D}_2(T)[\mathfrak{B}, \mathfrak{B}].$ We also
compute the determinant of $\mathfrak{D}$ and show that its absolute
value is independent of the structure of $T$ and apply it to obtain the
inertia of $\mathfrak{D}_2(T)$.
This is joint work with Ali Azimi (Iran).

