A bound for the complexity of a simple graph (Q1102975)

From MaRDI portal
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
    0 references
    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
    0 references
    complexity of a graph
    0 references
    spanning trees
    0 references
    0 references