The distance matrix and its variants for graphs and digraphs

2021-01-01
Authors
Reinhart, Carolyn
Leslie Hogben
Organizational Units
Organizational Unit
Mathematics
Abstract

The distance matrix $\mathcal{D}(G)$ of a connected graph $G$ is the matrix whose entries are the pairwise distances between vertices. The distance matrix was defined by Graham and Pollak in 1971 in order to study the problem of loop switching in routing messages through a network. Since then, variants such as the distance Laplacian and distance signless Laplacian have been introduced and studied. This dissertation will study various properties of the distance matrix and its Laplacians.

First, a new distance matrix variant, the normalized distance Laplacian, denoted $\mathcal{D}^{\mathcal {L}}(G)$, is introduced and is defined analogously to the normalized Laplacian matrix, $\mathcal{L}(G)$. Bounds on the $\mathcal{D}^{\mathcal {L}}(G)$ spectral radius and connections with the normalized Laplacian matrix are presented. The number of graphs with $\mathcal{D}^{\mathcal {L}}$-cospectral mates is determined for all graphs on 10 and fewer vertices, providing evidence that the normalized distance Laplacian has fewer cospectral pairs than other matrices.

Various graph parameters have been shown to be preserved or not preserved by cospectrality for the distance matrix and its variants. We summarize known results and show several parameters are not preserved by cospectrality for the distance matrix, the signless distance Laplacian, the distance Laplacian, and the normalized distance Laplacian. Furthermore, we prove that two transmission regular graphs which are distance cospectral must have the same transmission and thus the same Wiener index.

The distance matrix of a digraph is the matrix whose $ij$th entry is the distance from vertex $v_i$ to vertex $v_j$. In order for this matrix to be defined, we consider only strongly connected digraphs, i.e., digraphs for which there is a dipath from $v_i$ to $v_j$ for every pair of vertices. The number of digraphs with a distance cospectral mate is found for 6 and fewer vertices. A cospectral construction is described that produces pairs of distance cospectral digraphs from a digraph with certain structural properties.