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

From MaRDI portal
Revision as of 10:43, 19 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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