【作者】 周慧；

【导师】 张和平；

【作者基本信息】 兰州大学 ， 应用数学， 2013， 硕士

【摘要】 设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]的一个推广形式,从而得到了块只有奇圈和完全图的一类图的距离矩阵的逆的公式。最后,本文给出一些关于图的距离矩阵的行列式、逆、特征多项式的进一步的一些问题和注记。更多还原

【Abstract】 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.更多还原