An Analog of Matrix Tree Theorem for Signless Laplacians

Document Type

Article

Publication Date

1-2019

Abstract

A spanning tree of a graph is a connected subgraph on all vertices with the minimum number of edges. The number of spanning trees in a graph G is given by Matrix Tree Theorem in terms of principal minors of Laplacian matrix of G. We show a similar combinatorial interpretation for principal minors of signless Laplacian Q. We also prove that the number of odd cycles in G is less than or equal to det(Q)/4, where the equality holds if and only if G is a bipartite graph or an odd-unicyclic graph.

Comments

© 2025 Elsevier

Link to Full Text

Share

COinS