Edge-cuts leaving components of order at least three (Q1849951): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 05:55, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Edge-cuts leaving components of order at least three |
scientific article |
Statements
Edge-cuts leaving components of order at least three (English)
0 references
2 December 2002
0 references
A graph \(G\) is said to be \(\lambda_p\)-edge connected if there is a set of edges whose removal breaks the graph into connected components each of cardinality at least \(p\). The minimum cardinality of such a cut, if it exists, is the order-\(p\) edge connectivity of \(G\). Under the name of extraconnectivity, this notion was studied in a series of papers [see \textit{J. Fàbrega} and \textit{M. A. Fiol}, Discrete Math. 155, 49-57 (1996; Zbl 0857.05064) and the references therein]. In the present paper the authors prove that a graph \(G\) of order \(n\geq 6\) is \(\lambda_3\)-edge connected unless it consists of a vertex incident with a number of triangles and/or paths of length at most three, with one additional single exception when \(n=6\). Then they show that \(\lambda_3 (G)\) is at most the minimum number of edges emanating from a set of three vertices which induce a connected graph. It is pointed out that a similar statement is no longer true for \(p\geq 4\).
0 references
order-3 edge-connectivity
0 references
extraconnectivity
0 references