A Diagonalization Algorithm for the Distance Matrix of Cographs

Abstract

Cographs is a well-known class of graphs in graph theory, which can be generated from a single vertex by applying a series of complement (or equivalently join operations) and disjoint union operations. The distance spectrum of graphs is a rather active topic in spectral graph theory these years. This paper denotes to revealing some properties for the distance spectrum of cographs. More precisely, we present an algorithm, using $O(n)$ time and space, to diagonalize the distance matrix of cographs, from which one can deduce a diagonal matrix congruent to matrix $D + \lambda I$ , where $D$ is the distance matrix of a cograph, $\lambda $ is a real number, and $I$ is the identity matrix. Besides, we also give some applications of such algorithm about the inertia of distance matrix of complete multipartite graphs.

Keywords

• Cograph
• cotree
• diagonalization algorithm
• distance eigenvalues
• distance matrix