Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 708.05057
Autor: Erdös, Paul; Faudree, Ralph J.; Gyárfás, A.; Schelp, R.H.
Title: Domination in colored complete graphs. (In English)
Source: J. Graph Theory 13, No.6, 713-718 (1989).
Review: A 2-colored graph G is a graph with edges colored red or blue. A set X\subset V(G) r-dominates (b-dominates) Y\subset V(G) if X\cap Y = Øand for each y in Y there exists x in X such that the edge (x,y) is red (blue). The set X\subset V(G) dominates Y\subset V(G) if either X r-dominates Y or X b-dominates Y. A set A on t vertices is said to dominate all but at most k vertices of G if A dominates B and |V(G)-A-B| \leq k. The following conjecture is due to the first author and A. Hajnal [Ramsey type theorems, Preprint (1987), Discrete Appl. Math. 25, No. ½, 37-52 (1989; Zbl 715.05052)]. For given positive integers n, t, any 2-colored complete graph Kn of order n has a set Xt of at most t vertices dominating all but at most n/2t vertices of Kn. The authors prove this conjecture by proving the following more general result. Let G = [X,Y] be a 2- colored complete bipartite graph, t be a nonnegative integer, and \beta in (0,1). Then at least one of the following two statements is true:
1. Some subset of at most t vertices of X r-dominates all but at most \betat+1(|X|+|Y|) vertices of Y.
2. Some subset of at most t vertices of Y b-dominates all but at most (1-\beta)t+1(|X|+|Y|) vertices of X.
The proof of this result is constructive, in fact, it is a greedy-type low-order polynomial algorithm which finds the required (red or blue) dominating set.
Reviewer: D.Lick
Classif.: * 05C99 Graph theory
68R10 Graph theory in connection with computer science
Keywords: r-domination; dominating set
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag