On stratification and domination in graphs

Ralucca Gera; Ping Zhang

Displaying similar documents to “On stratification and domination in graphs”

Set vertex colorings and joins of graphs

Futaba Okamoto, Craig W. Rasmussen, Ping Zhang (2009)

Czechoslovak Mathematical Journal

Similarity:

For a nontrivial connected graph $G$ , let $c V (G) \to ℕ$ be a vertex coloring of $G$ where adjacent vertices may be colored the same. For a vertex $v$ of $G$ , the neighborhood color set $NC (v)$ is the set of colors of the neighbors of $v$ . The coloring $c$ is called a set coloring if $NC (u) \neq NC (v)$ for every pair $u, v$ of adjacent vertices of $G$ . The minimum number of colors required of such a coloring is called the set chromatic number $χ_{s} (G)$ . A study is made of the set chromatic number of the join $G + H$ of two graphs $G$ and $H$ . Sharp lower...

Realizable triples for stratified domination in graphs

Ralucca Gera, Ping Zhang (2005)

Mathematica Bohemica

Similarity:

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...

On the dominator colorings in trees

Houcine Boumediene Merouane, Mustapha Chellali (2012)

Discussiones Mathematicae Graph Theory

Similarity:

In a graph G, a vertex is said to dominate itself and all its neighbors. A dominating set of a graph G is a subset of vertices that dominates every vertex of G. The domination number γ(G) is the minimum cardinality of a dominating set of G. A proper coloring of a graph G is a function from the set of vertices of the graph to a set of colors such that any two adjacent vertices have different colors. A dominator coloring of a graph G is a proper coloring such that every vertex of V dominates...

Homogeneously embedding stratified graphs in stratified graphs

Gary Chartrand, Donald W. Vanderjagt, Ping Zhang (2005)

Mathematica Bohemica

Similarity:

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^{'}$ of $H$ containing $y$ and a color-preserving...

Radio number for some thorn graphs

Ruxandra Marinescu-Ghemeci (2010)

Discussiones Mathematicae Graph Theory

Similarity:

For a graph G and any two vertices u and v in G, let d(u,v) denote the distance between u and v and let diam(G) be the diameter of G. A multilevel distance labeling (or radio labeling) for G is a function f that assigns to each vertex of G a positive integer such that for any two distinct vertices u and v, d(u,v) + |f(u) - f(v)| ≥ diam(G) + 1. The largest integer in the range of f is called the span of f and is denoted span(f). The radio number of G, denoted rn(G), is the minimum span...