图的距离矩阵的行列式和逆
摘要
设Tn是一个有n个顶点的树,D(Tn)是它的距离矩阵。Graham和Pollak[8]证明了det(D(Τn))=(-1)n-12n-2(n-1)。这个公式称为Graham-Pollak公式,它只和树的顶点数有关,而与树的结构无关。关于Graham-Pollak公式的推广可参见文献[2,4,9]。一个图的极大二连通子图称为一个块。本文分析了图的距离矩阵的行列式的性质,并计算了层叠图Layer(G,K),Hamming图H(q,n),超立方Qn,联图G∨H,完全二部图Km,n,块儿只有奇圈和完全图的图,笛卡尔积Pm×Pn和Pm×C2n的距离矩阵的行列式。从而得到Graham-Pollak公式的一个推广。本文还得到了Bapat定理[4]的一个推广形式,从而得到了块只有奇圈和完全图的一类图的距离矩阵的逆的公式。最后,本文给出一些关于图的距离矩阵的行列式、逆、特征多项式的进一步的一些问题和注记。
Let Tn be a tree on n vertices and D(Tn) its distance matrix. Graham and Pollak [8] showed that det(D(Tn))=(-l)n-12n-1), which only depends on the number of vertices of the tree, but has nothing to do with the structure. Various generalizations of Graham and Pollak's formula can be found in [2,4,9]. A block of a graph is a maximal2-connected subgraph. This paper analyses the properties of determinant of distance matrix of a graph and calculates the de-terminants of distance matrices of the layer graph Layer(G, k)(see definition in section2.1), Hamming graphs H(q,n)(as a special case the hypercubes Qn), the joint graph GV H, the complete bipartite graph Km,n, graphs whose blocks are odd cycles and cliques, the cartesian product Pm x Pn and Pm x C2n. And then we get a generalization of Graham and Pollak's formula. We get a generalization of Bapat's theorem [4], and then give the formula of the inverse of distance matrix of a graph whose blocks are odd cycles and cliques. At last, we give some further problems and notes on the determinant, inverse and characteristic polynomial of the distance matrix of a graph.
Let Tn be a tree on n vertices and D(Tn) its distance matrix. Graham and Pollak [8] showed that det(D(Tn))=(-l)n-12n-1), which only depends on the number of vertices of the tree, but has nothing to do with the structure. Various generalizations of Graham and Pollak's formula can be found in [2,4,9]. A block of a graph is a maximal2-connected subgraph. This paper analyses the properties of determinant of distance matrix of a graph and calculates the de-terminants of distance matrices of the layer graph Layer(G, k)(see definition in section2.1), Hamming graphs H(q,n)(as a special case the hypercubes Qn), the joint graph GV H, the complete bipartite graph Km,n, graphs whose blocks are odd cycles and cliques, the cartesian product Pm x Pn and Pm x C2n. And then we get a generalization of Graham and Pollak's formula. We get a generalization of Bapat's theorem [4], and then give the formula of the inverse of distance matrix of a graph whose blocks are odd cycles and cliques. At last, we give some further problems and notes on the determinant, inverse and characteristic polynomial of the distance matrix of a graph.
引文
[1]R. B. Bapat, Determinant of the distance matrix of a tree with matrix weights, Linear Algebra Appl.416 (2006) 2-7.
[2]R. B. Bapat, S. J. Kirkland, M. Neumann, On distance matrices and Laplacians, Linear Algebra Appl.401 (2005) 193-209.
[3]R. B. Bapat, A. K. Lal and Sukanta Pati, A q-analogue of the distance matrix of a tree, Linear Algebra Appl.416 (2006) 799-814.
[4]R. B. Bapat, Sivaramakrishnan Sivasubramanian, Inverse of the distance matrix of a block graph, Linear and Multillinear Algebra 59 (2011) 1393-1397.
[5]M. Edelberg, M. R. Garey and R. L. Graham, On the distance matrix of a tree, Discrete Math.14 (1976) 23-39.
[6]R. L. Graham, A. J. Hoffman and H. Hosoya, On the distance matrix of a directed graph, J. Graph Theory 1 (1977),85-88.
[7]R. L. Graham and L. Lovasz, Distance matrix polynomials of trees, Adv. Math.29 (1978) 60-88.
[8]R. L. Graham and H. O. Pollak, On the addressing problem for loop switching. Bell Sys. Tech. J.50 (1971) 2495-2519.
[9]S. Sivasubramanian, q-Analogs of distance matrices of hypertrees, Linear Algebra Appl.431 (2009) 1234-1248.
[10]Weigen Yan and Yeong-Nan Yeh, Note:A simple proof of Graham and Pollak's Theorem, J. of Combin. Theory, Series A 113 (2006) 892-893.
[2]R. B. Bapat, S. J. Kirkland, M. Neumann, On distance matrices and Laplacians, Linear Algebra Appl.401 (2005) 193-209.
[3]R. B. Bapat, A. K. Lal and Sukanta Pati, A q-analogue of the distance matrix of a tree, Linear Algebra Appl.416 (2006) 799-814.
[4]R. B. Bapat, Sivaramakrishnan Sivasubramanian, Inverse of the distance matrix of a block graph, Linear and Multillinear Algebra 59 (2011) 1393-1397.
[5]M. Edelberg, M. R. Garey and R. L. Graham, On the distance matrix of a tree, Discrete Math.14 (1976) 23-39.
[6]R. L. Graham, A. J. Hoffman and H. Hosoya, On the distance matrix of a directed graph, J. Graph Theory 1 (1977),85-88.
[7]R. L. Graham and L. Lovasz, Distance matrix polynomials of trees, Adv. Math.29 (1978) 60-88.
[8]R. L. Graham and H. O. Pollak, On the addressing problem for loop switching. Bell Sys. Tech. J.50 (1971) 2495-2519.
[9]S. Sivasubramanian, q-Analogs of distance matrices of hypertrees, Linear Algebra Appl.431 (2009) 1234-1248.
[10]Weigen Yan and Yeong-Nan Yeh, Note:A simple proof of Graham and Pollak's Theorem, J. of Combin. Theory, Series A 113 (2006) 892-893.