On elements in small cocircuits in minimally \(k\)-connected graphs and matroids (Q5957720)
From MaRDI portal
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