Computing the Determinant of the Distance Matrix of a Bicyclic Graph

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

Belo Horizonte

Congreso; X Latin American Algorithms, Graphs, and Optimization Symposium; 2019

Unversidad Federal de Minas Gerais

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