Recognizable colorings of cycles and trees

Michael J. Dorfling; Samantha Dorfling

The search session has expired. Please query the service again.

Displaying similar documents to “Recognizable colorings of cycles and trees”

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

Recognizable colorings of graphs

Gary Chartrand, Linda Lesniak, Donald W. VanderJagt, Ping Zhang (2008)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a connected graph and let c:V(G) → 1,2,...,k be a coloring of the vertices of G for some positive integer k (where adjacent vertices may be colored the same). The color code of a vertex v of G (with respect to c) is the ordered (k+1)-tuple code(v) = (a₀,a₁,...,aₖ) where a₀ is the color assigned to v and for 1 ≤ i ≤ k, $a_{i}$ is the number of vertices adjacent to v that are colored i. The coloring c is called recognizable if distinct vertices have distinct color codes and the recognition...

Rainbow connection in graphs

Gary Chartrand, Garry L. Johns, Kathleen A. McKeon, Ping Zhang (2008)

Mathematica Bohemica

Similarity:

Let $G$ be a nontrivial connected graph on which is defined a coloring $c E (G) \to {1, 2, ..., k}$ , $k \in ℕ$ , of the edges of $G$ , where adjacent edges may be colored the same. A path $P$ in $G$ is a rainbow path if no two edges of $P$ are colored the same. The graph $G$ is rainbow-connected if $G$ contains a rainbow $u - v$ path for every two vertices $u$ and $v$ of $G$ . The minimum $k$ for which there exists such a $k$ -edge coloring is the rainbow connection number $r c (G)$ of $G$ . If for every pair $u, v$ of distinct vertices, $G$ contains a rainbow $u - v$ geodesic,...

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

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

Multicolor Ramsey numbers for paths and cycles

Tomasz Dzido (2005)

Discussiones Mathematicae Graph Theory

Similarity:

For given graphs G₁,G₂,...,Gₖ, k ≥ 2, the multicolor Ramsey number R(G₁,G₂,...,Gₖ) is the smallest integer n such that if we arbitrarily color the edges of the complete graph on n vertices with k colors, then it is always a monochromatic copy of some $G_{i}$ , for 1 ≤ i ≤ k. We give a lower bound for k-color Ramsey number R(Cₘ,Cₘ,...,Cₘ), where m ≥ 8 is even and Cₘ is the cycle on m vertices. In addition, we provide exact values for Ramsey numbers R(P₃,Cₘ,Cₚ), where P₃ is the path on 3 vertices,...

The multiset chromatic number of a graph

Gary Chartrand, Futaba Okamoto, Ebrahim Salehi, Ping Zhang (2009)

Mathematica Bohemica

Similarity:

A vertex coloring of a graph $G$ is a multiset coloring if the multisets of colors of the neighbors of every two adjacent vertices are different. The minimum $k$ for which $G$ has a multiset $k$ -coloring is the multiset chromatic number $χ_{m} (G)$ of $G$ . For every graph $G$ , $χ_{m} (G)$ is bounded above by its chromatic number $χ (G)$ . The multiset chromatic number is determined for every complete multipartite graph as well as for cycles and their squares, cubes, and fourth powers. It is conjectured that for each $k \geq 3$ , there...