On the minor-minimal 2-connected graphs having a fixed minor (Q1827674): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 10:56, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the minor-minimal 2-connected graphs having a fixed minor |
scientific article |
Statements
On the minor-minimal 2-connected graphs having a fixed minor (English)
0 references
6 August 2004
0 references
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\).
0 references
2-Connected graph
0 references
Graph minor
0 references
Block
0 references