Extraconnectivity of graphs with large minimum degree and girth (Q1356447)

From MaRDI portal
Revision as of 14:23, 31 January 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
Extraconnectivity of graphs with large minimum degree and girth
scientific article

    Statements

    Extraconnectivity of graphs with large minimum degree and girth (English)
    0 references
    0 references
    9 November 1997
    0 references
    The extraconnectivity \(\kappa (n)\) of a graph \(G\) is the minimum cardinality of a set of vertices, if any, whose deletion disconnects \(G\) in such a way that every remaining component has more than \(n\) vertices. The edge-extraconnectivity \(\lambda (n)\) is defined similarly. The paper brings sufficient conditions for maximum (edge-)extraconnectivity. One of them relates the diameter \(D\), the girth \(g\) and the minimum degree \(\delta\): If \(D\leq g-n+2 (\delta-3)\) for \(n\geq 2\delta+4\) and \(g\geq n+5\), then \(\kappa(n) =(n+1) \delta- 2n\), which is the maximum.
    0 references
    0 references
    extraconnectivity
    0 references
    edge-extraconnectivity
    0 references
    diameter
    0 references
    girth
    0 references
    minimum degree
    0 references

    Identifiers