On the determinant of distance matrices of graphs

Yen-Jen Cheng

Department of Mathematics

National Taiwan Normal University


    For a connected graph `G=(V;E)`, the distance matrix `D(G)=(d_{ij})` is a square matrix with index set `V` and `d_{ij}` the distance between `i` and `j`. In 1971, Graham and Pollak proved that if `T` is a tree, then `\det(D(T))` only depends on the order of `T`. In this talk, I will give new classes of graphs such that `\det(D(G))` is a constant among each class. In addition, I will introduce the addressing problem and find the addressing number for these new graphs. This is a joint work with Jephian Chin-Hung Lin.

Keyword: CP graph, distance matrix, determinant, inertia


[1] R. B. Bapat. Graphs and Matrices. Second edition. Springer 2014. (Chapter 9)
[2] R. B. Bapat and S. Sivasubramanian. The second immanant of some com- binatorial matrices. Trans. Comb., 4 (2015) 23-35.
[3] Y.-J. Cheng and J. C.-H. Lin. On the distance matrices of the CP graphs. ArXiv:1805.10269, submitted.
[4] J. H. van Lint and R. M. Wilson. A Course in Combinatorics. Second edition. Cambridge 2001. (Chapter 9)