On the minor-minimal 2-connected graphs having a fixed minor (Q1827674): Difference between revisions

A block of a graph \(G\) is a maximal connected subgraph \(H\) so that every two distinct edges of \(H\) lie on a cycle. For a graph \(G\), \(\kappa_1(G)\) denotes the number of connected components of \(G\) and \(\kappa_2(G)\) denotes the number of blocks of \(G\). The main result of this paper is: Theorem 1.1. Let \(\alpha\) and \(\beta\) be real numbers. Then, for all graphs \(G\) and \(H\) such that \(G\) is a minor-minimal 2-connected graph having \(H\) as a minor, \[ | E(G)|-| E(H)|\leq \alpha(\kappa_1(H)- 1)+ \beta(\kappa_2(H)- 1) \] if and only if \(\alpha+\beta\geq 5\), \(2\alpha+ 5\beta\geq 20\) and \(\beta\geq 3\).