On the dominator colorings in trees

Houcine Boumediene Merouane; Mustapha Chellali

Displaying similar documents to “On the dominator colorings in trees”

Defining sets in (proper) vertex colorings of the Cartesian product of a cycle with a complete graph

D. Ali Mojdeh (2006)

Discussiones Mathematicae Graph Theory

Similarity:

In a given graph G = (V,E), a set of vertices S with an assignment of colors to them is said to be a defining set of the vertex coloring of G, if there exists a unique extension of the colors of S to a c ≥ χ(G) coloring of the vertices of G. A defining set with minimum cardinality is called a minimum defining set and its cardinality is the defining number, denoted by d(G,c). The d(G = Cₘ × Kₙ, χ(G)) has been studied. In this note we show that the exact value of defining number d(G =...

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

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

On stratification and domination in graphs

Ralucca Gera, Ping Zhang (2006)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class), 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 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...

Recognizable colorings of cycles and trees

Michael J. Dorfling, Samantha Dorfling (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For a graph G and a vertex-coloring c:V(G) → 1,2, ...,k, the color code of a vertex v is the (k+1)-tuple (a₀,a₁, ...,aₖ), where a₀ = c(v), and for 1 ≤ i ≤ k, $a_{i}$ is the number of neighbors of v colored i. A recognizable coloring is a coloring such that distinct vertices have distinct color codes. The recognition number of a graph is the minimum k for which G has a recognizable k-coloring. In this paper we prove three conjectures of Chartrand et al. in [8] regarding the recognition number...

Graph colorings with local constraints - a survey

Zsolt Tuza (1997)

Discussiones Mathematicae Graph Theory

Similarity:

We survey the literature on those variants of the chromatic number problem where not only a proper coloring has to be found (i.e., adjacent vertices must not receive the same color) but some further local restrictions are imposed on the color assignment. Mostly, the list colorings and the precoloring extensions are considered. In one of the most general formulations, a graph G = (V,E), sets L(v) of admissible colors, and natural numbers $c_{v}$ for the vertices v ∈ V are given, and the question...

A new upper bound for the chromatic number of a graph

Ingo Schiermeyer (2007)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph of order n with clique number ω(G), chromatic number χ(G) and independence number α(G). We show that χ(G) ≤ [(n+ω+1-α)/2]. Moreover, χ(G) ≤ [(n+ω-α)/2], if either ω + α = n + 1 and G is not a split graph or α + ω = n - 1 and G contains no induced $K_{ω + 3} - C ₅$ .

On detectable colorings of graphs

Henry Escuadro, Ping Zhang (2005)

Mathematica Bohemica

Similarity:

Let $G$ be a connected graph of order $n \geq 3$ and let $c E (G) \to {1, 2, ..., k}$ be a coloring of the edges of $G$ (where adjacent edges may be colored the same). For each vertex $v$ of $G$ , the color code of $v$ with respect to $c$ is the $k$ -tuple $c (v) = (a_{1}, a_{2}, \dots, a_{k})$ , where $a_{i}$ is the number of edges incident with $v$ that are colored $i$ ( $1 \leq i \leq k$ ). The coloring $c$ is detectable if distinct vertices have distinct color codes. The detection number $det (G)$ of $G$ is the minimum positive integer $k$ for which $G$ has a detectable $k$ -coloring. We establish a formula for the...

Radio antipodal colorings of graphs

Gary Chartrand, David Erwin, Ping Zhang (2002)

Mathematica Bohemica

Similarity:

A radio antipodal coloring of a connected graph $G$ with diameter $d$ is an assignment of positive integers to the vertices of $G$ , with $x \in V (G)$ assigned $c (x)$ , such that $d (u, v) + | c (u) - c (v) | \geq d$ for every two distinct vertices $u$ , $v$ of $G$ , where $d (u, v)$ is the distance between $u$ and $v$ in $G$ . The radio antipodal coloring number $a c (c)$ of a radio antipodal coloring $c$ of $G$ is the maximum color assigned to a vertex of $G$ . The radio antipodal chromatic number $a c (G)$ of $G$ is $min {a c (c)}$ over all radio antipodal colorings $c$ of $G$ . Radio antipodal chromatic numbers...