| In this thesis we combine the idea of stratification with the one of domination in graphs and digraphs, respectively.; A graph is 2-stratified if its vertex set is partitioned into two classes, where the vertices in one class are colored red and those in the other class are colored blue. Let F be a 2-stratified graph rooted at some blue vertex v. An F-coloring of a graph G is a red-blue coloring of the vertices of G in which every blue vertex u belongs to a copy of F rooted at u. The F-domination number gammaF(G) is the minimum number of red vertices in an F-coloring of G.; It is shown in Chapter 3 that (1) for each pair a, b of positive integers, there exists a connected graph G such that gamma(G) = a and gamma F(G) = b; (2) for each pair a, b of positive integers with a ≥ 2, there exists a connected graph G such that gamma o(G) = a and gamma F(G) = b; (3) for each pair a, b of positive integers with a ≤ b, there exists a connected graph G such that gamma ∃2(G) = a and gamma F(G) = b if and only if ( a, b) ≠ (1, i) for some i ≥ 2; and (4) for each pair a, b of positive integers with a ≤ b, there exists a connected graph G with gammaF(G) = a and gammar(G) = b. In Chapter 4, we show that a triple ( A,B,C ) of positive integers with A≤B≤2A and B ≥ 2 is realizable as the domination number, open domination number, and F-domination number, respectively, for some connected graph if and only if ( A,B,C ) ≠ (k, k, C ) for integers k and C with C > k ≥ 2.; In Chapter 5, H-domination is studied where H is the red-red-blue directed path of order 3. We study relationships between the H-domination number gammaH and both the domination number gamma and open domination gamma o in digraphs. (Abstract shortened by UMI.)... |
