A bound for the complexity of a simple graph (Q1102975): Difference between revisions
From MaRDI portal
Changed an Item |
Created claim: Wikidata QID (P12): Q126594505, #quickstatements; #temporary_batch_1719407511203 |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4770409 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An inequality for the second immanant / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Fischer inequality for the second immanant / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An upper bound for the number of spanning trees of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Spanning trees in regular graphs / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q126594505 / rank | |||
Normal rank |
Latest revision as of 15:13, 26 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A bound for the complexity of a simple graph |
scientific article |
Statements
A bound for the complexity of a simple graph (English)
0 references
1988
0 references
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)}. \]
0 references
complexity of a graph
0 references
spanning trees
0 references