A note on fragile graphs (Q1598838)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A note on fragile graphs
scientific article

    Statements

    A note on fragile graphs (English)
    0 references
    0 references
    0 references
    28 May 2002
    0 references
    The authors prove the conjecture of Y. Caro that every graph on \(n\) vertices and at most \(2n-4\) edges contains an independent vertex-cut. The result is best possible, since the graph obtained from \(K_{2,n-2}\) by adding an edge between vertices of the part with just two vertices, has \(n\) vertices and \(2n-3\) edges, while none of its vertex-cuts is independent.
    0 references
    graph
    0 references
    independence number
    0 references
    vertex-cut
    0 references
    conjecture
    0 references

    Identifiers