An analog of Matrix Tree Theorem for signless Laplacians

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.