The number of cutvertices in graphs with given minimum degree (Q912123)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The number of cutvertices in graphs with given minimum degree |
scientific article |
Statements
The number of cutvertices in graphs with given minimum degree (English)
0 references
1990
0 references
Let h(n,d) denote the maximum number of cutvertices in a connected graph of order n having minimum degree at least d. The authors show that for \(n-1d>\geq 5\), \[ h(n,d)=2\lfloor \frac{n}{d+1}\rfloor +2\lfloor \frac{n}{(d+1)(d^ 2-2)}\rfloor +e(n), \] where e(n) is well-defined and \(\epsilon\) \(\{\)-3,-2,-1,0\(\}\).
0 references
maximum number of cutvertices
0 references
minimum degree
0 references