Transformations of a graph increasing its Laplacian polynomial and number of spanning trees
type: Item
instance of: scholarly article
title: Transformations of a graph increasing its Laplacian polynomial and number of spanning trees
zbMATH Open document ID: 0873.05065
author: Alexander Kelmans
published in: European Journal of Combinatorics
publication date: 1997-10-20T00:00:00Z
review text: 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)\).
reviewed by: Dragoš Cvetković
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 980796
zbMATH Keywords: number of spanning trees
zbMATH Keywords: characteristic polynomial
zbMATH Keywords: Laplacian matrix
zbMATH Keywords: graph transformations
zbMATH Keywords: extremal problems
MaRDI profile type: Publication
full work available at URL: eujc.1995.0077
OpenAlex ID: W1994508421
DOI: 10.1006/EUJC.1995.0077
Recommended article: Laplacian polynomial and number of spanning trees in terms of characteristic polynomial of induced subgraphs
Recommended article: On the Laplacian coefficients of graphs under some transformations
Recommended article: Spanning tree enumeration and nearly triangular graph Laplacians
Recommended article: Adjacency polynomials of digraph transformations
Recommended article: Transforming spanning trees and pseudo-triangulations
Recommended article: Q3734421
Recommended article: Transforming spanning trees: A lower bound
Recommended article: Laplacian matrices and spanning trees of tree graphs
Recommended article: The Laplacian polynomial of complete multipartite graphs
Recommended article: On polynomials of spanning trees
description: scientific article; zbMATH DE number 980796