An Analog of Matrix Tree Theorem for Signless Laplacians
| Autor: | Sudipta Mallik, Keivan Hassani Monfared |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Numerical Analysis
Algebra and Number Theory Spanning tree Combinatorial interpretation 010102 general mathematics Vertex connectivity 010103 numerical & computational mathematics Signless laplacian 01 natural sciences Graph Combinatorics Bipartite graph FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Matrix tree theorem Geometry and Topology Combinatorics (math.CO) 0101 mathematics Laplacian matrix Mathematics 05C50 65F18 |
| DOI: | 10.48550/arxiv.1805.04759 |
| Popis: | 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 $\frac{\det(Q)}{4}$, where the equality holds if and only if $G$ is a bipartite graph or an odd-unicyclic graph. Comment: 16 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|