Computing the Determinant of the Distance Matrix of a Bicyclic Graph

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

Belo Horizonte

Congreso; LAGOS'19 - X Latin and American Algorithms, Graphs and Optimization; 2019

Let G be a connected graph with vertex set V = {v1, ..., vn}. The distance d(vi, vj) between two vertices vi and vj is the number of edges of a shortest path linking them. The distance matrix of G is the n × n matrix such that its (i, j)-entry is equal to d(vi, vj). A formula to compute the determinant of this matrix in terms of the number of vertices was found when the graph either is a tree or is a unicyclic graph. For a byciclic graph, the determinant is known in the case where the cycles have no common edges. In this paper, we present some advances for the remaining cases; i.e., when the cycles share at least one edge. We also present a conjecture for the unsolved cases.