Computing the determinant of the distance matrix of a bicylic graph

CELSO M. DA SILVA JR; RENATA R. DEL-VECCHIO; EZEQUIEL DRATMAN; LUCIANO N. GRIPPO; MARTÍN D. SAFE

Niterói

Workshop; LAAW 2018; 2018

Let $G$ be a connected graph with vertex set $V=\{1,\ldots,n\}$. The \emph{distance} between two vertices $i$ and $j$, denoted $d(i,j)$, is the number of edges of a shortest path linking them. The \emph{distance matrix} of $G$ is the $n\times n$ matrix such that its $(i,j)$-entry is equal to $d(i,j)$. Graham and Pollack [3] found a formula to compute the determinant of the distance matrix of a tree on $n$ vertices, an acyclic and connected graph, depending only of $n$. Then, Bapat, Kirkland and Neumann [1] proved that the determinant of the distance matrix of a unicyclic graph, a connected graph with as many edges as vertices, depends on the length of the cycle and the number of its vertices. In an attempt to get an expression for the determinant of the distance matrix of a bicyclic graph, Gong, Zhang, and Xu [2] considered those bicyclic graphs having two edge-disjoint cycles, where a \emph{bicyclic graph} on $n$ vertices is a connected graph having $n+1$ edges. To the best of our knowledge, finding a formula for the determinant of he distance matrix of any bicyclic graph remains as an open problem. In this work, we will present new advances towards covering the remainder cases.