A 2-stratified graph G is a graph whose vertex set has been partitioned into two subsets, called the strata or color classes of G. Two 2-stratified graphs G and H are isomorphic if there exists a color-preserving isomorphism ϕ from G to H. A 2-stratified graph G is said to be homogeneously embedded in a 2-stratified graph H if for every vertex x of G and every vertex y of H, where x and y are colored the same, there exists an induced 2-stratified subgraph H 0 of H containing y and a color-preserving isomorphism ϕ from G to H0 such that ϕ(x) = y. A 2-stratified graph F of minimum order in which G can be homogeneously embedded is called a frame of G and the order of F is called the framing number fr(G) of G. It is shown that every 2-stratified graph can be homogeneously embedded in some 2-stratified graph. For a graph G, a 2-stratified graph F of minimum order in which every 2-stratification of G can be homogeneously embedded is called a fence of G and the order of F is called the fencing number fe(G) of G. The fencing numbers of some well-known classes of graphs are determined. It is shown that if G is a vertex-transitive graph of order n that is not a complete graph then fe(G) = 2n.
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 v belongs to a copy of F rooted at v. The F-domination number γF (G) is the minimum number of red vertices in an F-coloring of G. In this paper, we study F-domination where F is a red-blue-blue path of order 3 rooted at a blue end-vertex. It is shown 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 any integers k and C with C > k ≥ 2.