Transformations of a graph increasing its Laplacian polynomial and number of spanning trees
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)\).
- Laplacian polynomial and number of spanning trees in terms of characteristic polynomial of induced subgraphs
- On the Laplacian coefficients of graphs under some transformations
- Spanning tree enumeration and nearly triangular graph Laplacians
- Adjacency polynomials of digraph transformations
- Transforming spanning trees and pseudo-triangulations
- scientific article; zbMATH DE number 3966096
- Transforming spanning trees: A lower bound
- Laplacian matrices and spanning trees of tree graphs
- The Laplacian polynomial of complete multipartite graphs
- On polynomials of spanning trees
- Solutions of some further graph equations
- Maximizing the total number of spanning trees in a graph: two related problems in graph theory and optimum design theory
- Tree counting polynomials for labelled graphs. I: Properties
- Comparison of graphs by their number of spanning trees
- Nonisomorphic trees with the same T-polynomial
- On the distribution of eigenvalues of graphs
- A certain polynomial of a graph and graphs with an extremal number of trees
- Tracking network dynamics: a survey using graph distances
- Laplacian spectra and spanning trees of threshold graphs
- On the Laplacian coefficients of graphs under some transformations
- Laplacian spectra of digraph transformations
- Spectra of digraph transformations
- Detection of core-periphery structure in networks using spectral methods and geodesic paths
- scientific article; zbMATH DE number 2188327 (Why is no real title available?)
- Multiplicative submodularity of a matrix's principal minor as a function of the set of its rows and some combinatorial applications
- Schur convex functions on the spectra of graphs
This page was built for publication: Transformations of a graph increasing its Laplacian polynomial and number of spanning trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5961460)
