Domination, packing and excluded minors
type: Item
instance of: scholarly article
title: Domination, packing and excluded minors
zbMATH Open document ID: 1024.05066
author: T. Böhme
author: Bojan Mohar
published in: The Electronic Journal of Combinatorics
publication date: 2003-09-24T00:00:00Z
full work available at URL: https://eudml.org/doc/122992
full work available at URL: v10i1n9.html
review text: 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.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C83
zbMATH DE Number: 1985384
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1985384