The Spectral Geometry of the Mesh Matrices of Graphs

Publication date 22 May 2023

Trees (05C05) Enumeration in graph theory (05C30) Simple homotopy type, Whitehead torsion, Reidemeister-Franz torsion, etc. (57Q10) Applications of graph theory to circuits and networks (94C15)

Abstract: The mesh matrix

M e s h (G, T_{0})

of a connected finite graph

G = (V (G), E (G)) = (v e r t i c e s, e d g e s) o f G

of with respect to a choice of a spanning tree

T_{0} s u b s e t G

is defined and studied. It was introduced by Trent cite{Trent1,Trent2}. Its characteristic polynomial

d e t (X c d o t I d - M e s h (G, T_{0}))

is shown to equal

S i g m a_{j = 0}^{N} (- 1)^{j} S T_{j} (G, T_{0}) (X - 1)^{N - j} (s t a r)

where

S T_{j} (G, T_{0})

is the number of spanning trees of

G

meeting

E (G - T_{0})

in j edges and

N = | E (G - T_{0}) |

. As a consequence, there are Tutte-type deletion-contraction formulae for computing this polynomial. Additionally,

M e s h (G, T_{0}) - I d

is of the special form

Y^{t} c d o t Y

; so the eigenvalues of the mesh matrix

M e s h (G, T_{0})

are all real and are furthermore be shown to be

g e + 1

. It is shown that

Y c d o t Y^{t}

, called the mesh Laplacian, is a generalization of the standard graph Kirchhoff Laplacian

D e l t a (H) = D e g - A d j

of a graph

H

.For example,

(s t a r)

generalizes the all minors matrix tree theorem for graphs

H

and gives a deletion-contraction formula for the characteristic polynomial of

D e l t a (H)

. This generalization is explored in some detail. The smallest positive eigenvalue of the mesh Laplacian, a measure of flux, is estimated, thus extending the classical inequality for the Kirchoff Laplacian of graphs.

This page was built for publication: The Spectral Geometry of the Mesh Matrices of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6437588)