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
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