Combinatorics, Probability and Computing

Research Article

Walk Generating Functions, Christoffel-Darboux Identities and the Adjacency Matrix of a Graph

C. D. Godsila1

a1 Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

Abstract

In this work we show that that many of the basic results concerning the theory of the characteristic polynomial of a graph can be derived as easy consequences of a determinantal identity due to Jacobi. As well as improving known results, we are also able to derive a number of new ones. A combinatorial interpretation of the Christoffel-Darboux identity from the theory of orthogonal polynomials is also presented. Finally, we extend some work of Tutte on the reconstructibility of graphs with irreducible characteristic polynomials.

(Received November 04 1991)

Footnotes

† This work was supported by NSERC grant A5367.