A bound for the complexity of a simple graph

DOI10.1016/0012-365X(88)90182-3MaRDI QIDQ1102975zbMATH OpenWikidataFDO

Authors Russell Merris, Robert D. Grone

Publication date 1988

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(88)90182-3

zbMATH Keywords

complexity of a graphspanning trees

Mathematics Subject Classification ID

Trees (05C05)

Review text

In accordance with the title, a new upper bound for the number of spanning trees, the so-called complexity \(K(G)\), of a simple graph G is presented. If n denotes the number of vertices of G (with at least one edge) and \(d_ 1(G)\geq...\geq d_ n(G)\) is a degree sequence then \[ K(G)\leq (\frac{n}{n-1})^{n-1}\frac{\prod d_ i(G)}{\sum d_ i(G)}. \]

Recommendations

• On a certain complexity estimate in graph theory
• The complexity of finite graphs
• The linear complexity of a graph
• The linear complexity of a graph
• A complexity problem for Borel graphs
• On Graph Complexity
• scientific article; zbMATH DE number 219271
• scientific article; zbMATH DE number 3876594
• scientific article; zbMATH DE number 3874609
• scientific article; zbMATH DE number 3874608

Cites work

• A Fischer inequality for the second immanant
• An inequality for the second immanant
• An upper bound for the number of spanning trees of a graph
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• Spanning trees in regular graphs

Cited in

(22)

• On the geometry and Laplacian of a graph
• Tree and forest weights and their application to nonuniform random graphs
• On the likelihood of forests
• The minimum number of spanning trees in regular multigraphs
• Simple graph density inequalities with no sum of squares proofs
• The maximum number of spanning trees of a graph with given matching number
• A sharp upper bound for the number of spanning trees of a graph
• On family of graphs with minimum number of spanning trees
• On the form factor for the unitary group
• Graph complexity and the laplacian matrix in blocked experiments
• Sharp upper bounds for the number of spanning trees of a graph
• Upper bounds for the number of spanning trees of graphs
• Applications of multlinear algebra
• scientific article; zbMATH DE number 1161331 (Why is no real title available?)
• A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs
• The number of spanning trees of a graph with given matching number
• The number of spanning trees of a graph
• The number of bounded‐degree spanning trees
• Spanning trees: A survey
• Calculating the entropy and number of spanning trees of a complex network model
• Maximum number of spanning trees and connectivity: graphs with a fixed minimum degree and bipartite graphs
• Cubic graphs and quartic graphs with the minimum number of spanning forests

This page was built for publication: A bound for the complexity of a simple graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1102975)