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 ) → ℕ 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 ) ≠ 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...

Minus total domination in graphs

Hua Ming Xing, Hai-Long Liu (2009)

Czechoslovak Mathematical Journal

Similarity:

A three-valued function f V → { - 1 , 0 , 1 } defined on the vertices of a graph G = ( V , E ) is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. That is, for every v ∈ V , f ( N ( v ) ) ≥ 1 , where N ( v ) consists of every vertex adjacent to v . The weight of an MTDF is f ( V ) = ∑ f ( v ) , over all vertices v ∈ V . The minus total domination number of a graph G , denoted γ t - ( G ) , equals the minimum weight of an MTDF of G . In this paper, we discuss some properties of minus total domination on a graph...