Critically \((k,k)\)-connected graphs (Q1093652)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Critically \((k,k)\)-connected graphs |
scientific article |
Statements
Critically \((k,k)\)-connected graphs (English)
0 references
1987
0 references
A graph G, with vertex connectivity \(\kappa(G)\), minimum degree \(\delta(G)\), and complement \(\bar G,\) is critically \((k,k)\)-connected if \(\kappa(G)=\kappa(\bar G)=k\), and for each vertex v of G, either \(\kappa(G-v)=k-1\) or \(\kappa(\bar G-v)=k-1\). Theorem: If G is a critically \((k,k)\)-connected graph with \(k\geq 2\), \(\delta(G)\geq (3k-1)\), and \(\delta(\bar G)\geq (3k-1)\), then 3k\(\leq | V(G)| \leq 4k\). Moreover, it is also shown that the upper bound is sharp for \(k\geq 3\).
0 references
critically (k,k)-connected graph
0 references