The number of blocks of a graph with given minimum degree (Q2657452)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The number of blocks of a graph with given minimum degree |
scientific article |
Statements
The number of blocks of a graph with given minimum degree (English)
0 references
12 March 2021
0 references
Summary: A block of a graph is a nonseparable maximal subgraph of the graph. We denote by \(b\left( G\right)\) the number of block of a graph \(G\). We show that, for a connected graph \(G\) of order \(n\) with minimum degree \(k\geq1\), \(b\left( G\right)<\left( \left( 2 k - 3\right) / \left( k^2 - k - 1\right)\right)n\). The bound is asymptotically tight. In addition, for a connected cubic graph \(G\) of order \(n\geq14\), \(b\left( G\right)\leq\left( n / 2\right)-2\). The bound is tight.
0 references