Domination, packing and excluded minors. (English) Zbl 1024.05066

Böhme, Thomas; Mohar, Bojan

Electron. J. Comb. 10, Research paper N9, 6 p. (2003); printed version J. Comb. 10, No. 3 (2003).

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.

MSC:

05C69	Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C83	Graph minors