Transformations of a graph increasing its Laplacian polynomial and number of spanning trees (Q5961460)

Let \(t(G)\) be the number of spanning trees and \(L(\lambda, G)\) the characteristic polynomial of the Laplacian matrix of a graph \(G\). Let \(G^m_n\) be the set of graphs with \(n\) vertices and \(m\) edges. The author studies graph transformations \(Q\) such that \(G\in G^m_n\) implies \(Q(G)\in G^m_n\) and \(L(\lambda, G)\leq L(\lambda,Q(G))\) for \(\lambda\geq n\). Since \(t(K_s\backslash G)= s^{s-n-2}L(s,G)\) for \(s\geq n\), transformations \(Q\) increase also the number of spanning trees in the corresponding complementary graphs. This enables to handle some extremal problems involving \(t(G)\).