On elements in small cocircuits in minimally \(k\)-connected graphs and matroids (Q5957720): 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 00:49, 5 March 2024
scientific article; zbMATH DE number 1718963
Language | Label | Description | Also known as |
---|---|---|---|
English | On elements in small cocircuits in minimally \(k\)-connected graphs and matroids |
scientific article; zbMATH DE number 1718963 |
Statements
On elements in small cocircuits in minimally \(k\)-connected graphs and matroids (English)
0 references
19 June 2002
0 references
The authors prove that in a minimally \(k\)-connected graph \(G\) with \(n\) vertices and \(e\) edges, the number of edges that are incident to a vertex of degree \(k\) is at least \(\lfloor\frac{e+7}{2}\rfloor\), if \(k=2\) and \(e\geq 6\), \(\lceil\frac{2e+12}{3}\rceil\), if \(k=3\) and \(e\geq 14\), and \(\frac{(k-1)e+3k+1}{k}\), if \(k\geq 3\) and \(n\geq 4k\). The first two bounds are best possible and all extremal graphs are characterized. The last bound is asymptotically best possible. The results are edge-versions of known results due to Dirac, Halin and Mader about the number of vertices of degree \(k\) in a minimally \(k\)-critical graph. For \(k=2\) the authors generalize their bound to matroids and for \(k=3\) they mention a corresponding conjecture.
0 references
minimally \(k\)-connected graph
0 references
extremal graphs
0 references
matroid
0 references