A Note on the Zeta Function of a Graph

✍ Scribed by Sam Northshield

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 113 KB
• Volume: 74
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1998.1861

✦ Synopsis

The number of spanning trees in a finite graph is first expressed as the derivative (at 1) of a determinant and then in terms of a zeta function. This generalizes a result of Hashimoto to non-regular graphs.

1998 Academic Press

Let G be a finite graph. The complexity of G, denoted }, is the number of spanning trees in G. This quantity has long been known to be related to matrices associated with G (see ). When G is regular, Hashimoto [2] expressed } as a limit involving the zeta function of the graph and asked if his expression still holds for irregular graphs. In this note, we show that the answer is yes. In particular, we derive a formula for the complexity as the derivative of a determinant involving the adjacency matrix of the graph and use this and a generalized version of Ihara's theorem to get the desired result.

Let G be a graph with & vertices and = edges. A path is a sequence of vertices such that consecutive vertices share an edge (we do not require that all vertices are distinct). A path is said to be non-backtracking if a subsequence of the form ..., x, y, x, ... does not appear. A cycle is a finite path whose first and last vertices agree. We do not distinguish a starting point (for example, we consider the cycles (x, y, z, x) and ( y, z, x, y) to be the same). A cycle (considered as a sequence of edges) can be concatenated with itself several times giving rise to another cycle. Such cycles are called multiples of the original cycle. A cycle is called prime if it and all its multiples are non-backtracking and it is not a multiple of a strictly smaller cycle. Since we assume that G is not a tree, there are some prime cycles. Let Article No. TB981861 408 0095-8956Â98 25.00