Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Domination, packing and excluded minors"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Domination, packing and excluded minors | Domination packing and excluded minors Thomas Bohme i Institut fur Mathematik Technische Universitat Ilmenau Ilmenau Germany Bojan Mohar Department of Mathematics University of Ljubljana Ljubljana Slovenia Submitted Feb 6 2003 Accepted Aug 22 2003 Published Sep 8 2003 MR Subject Classifications 05C69 05C83 Abstract Let Y G be the domination number of a graph G and let ak G be the maximum number of vertices in G no two of which are at distance k in G. It is easy to see that Y G a2 G . In this note it is proved that Y G is bounded from above by a linear function in a2 G if G has no large complete bipartite graph minors. Extensions to other parameters ak G are also derived. 1 Introduction and main results Let G be a finite undirected graph. A graph H is a minor of G if it can be obtained from a subgraph of G by contracting edges. The distance distc x y in G of two vertices x y E V G is the length of a shortest x y -path in G. The distance of a vertex x from a set A c V G is min distc x a I a E A . For a set A c V G G A denotes the subgraph of G induced by A. If k is a nonnegative integer we denote by Nk A the set of all vertices of G which are at distance k from A. The set A is a k-dominating set in G if Nk A V G . The cardinality of a smallest k-dominating set of G is denoted by Yk G . A vertex set X0 c V G is an ak-set if no two vertices in X0 are at distance k in G. Let ak G denote the cardinality of a largest ak-set of G. Observe that Y G Y1 G and a G a1 G are the usual domination number and the independence or stability number of G. We refer to 3 for further details on domination in graphs. Supported by SLO-German grant SVN 99 003. E-mail address tboehme@theoinf.tu-ilmenau.de Supported in part by the Ministry of Education Science and Sport of Slovenia Research Project J1-0502-0101-00 and by SLO-German grant SVN 99 003. E-mail address bojan.mohar@uni-lj .si THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 N9 1 It is clear that Yk G a2k G . On the other hand for any