On the determinant of distance matrices of graphs

Yen-Jen Cheng

Department of Mathematics

National Taiwan Normal University

yjc7755@gmail.com

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

References

[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)