Domination, packing and excluded minors (Q1408550)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1985384
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Domination, packing and excluded minors |
scientific article; zbMATH DE number 1985384 |
Statements
Domination, packing and excluded minors (English)
0 references
24 September 2003
0 references
Summary: Let \(\gamma(G)\) be the domination number of a graph \(G\), and let \(\alpha_k(G)\) be the maximum number of vertices in \(G\), no two of which are at distance at most \(k\) in \(G\). It is easy to see that \(\gamma(G)\geq \alpha_2(G)\). In this note it is proved that \(\gamma(G)\) is bounded from above by a linear function in \(\alpha_2(G)\) if \(G\) has no large complete bipartite graph minors. Extensions to other parameters \(\alpha_k(G)\) are also derived.
0 references
0.7998616099357605
0 references
0.7994213104248047
0 references
0.7873586416244507
0 references
0.7869853973388672
0 references
0.786923348903656
0 references
