On the bipartite distance matrix and the bipartite Laplacian matrix

Abstract

The study of the properties of graphs via matrices is a widely studied subject that ties together two seemingly unrelated branches of mathematics; graph theory and linear algebra. Graham and Pollak in 1971 proved a remarkable result which tells that the determinant of the distance matrix of a tree only depends on the number of vertices in the tree. This impressive result created a lot of interest among the researchers. Since then many generalizations have been proposed in order to understand the distance matrix better. Yet, the understanding seems to be far from complete. We present one such point of view here showing how many more combinatorial objects are linked together.