Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Recognizable colorings of graphs

100%

Chartrand G., Lesniak L., VanderJagt D., Zhang P.

Discussiones Mathematicae Graph Theory

2008

tom 28

nr 1

35-57

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 number rn(G) of G is the minimum positive integer k for which G has a recognizable k-coloring. Recognition numbers of complete multipartite graphs are determined and characterizations of connected graphs of order n having recognition numbers n or n-1 are established. It is shown that for each pair k,n of integers with 2 ≤ k ≤ n, there exists a connected graph of order n having recognition number k. Recognition numbers of cycles, paths, and trees are investigated.

On γ-labelings of trees

100%

Chartrand G., Erwin D., VanderJagt D., Zhang P.

Discussiones Mathematicae Graph Theory

2005

tom 25

nr 3

363-383

Let G be a graph of order n and size m. A γ-labeling of G is a one-to-one function f:V(G) → {0,1,2,...,m} that induces a labeling f': E(G) → {1,2,...,m} of the edges of G defined by f'(e) = |f(u)-f(v)| for each edge e = uv of G. The value of a γ-labeling f is $val(f) = Σ_{e ∈ E(G)}f'K(e)$. The maximum value of a γ-labeling of G is defined as $val_{max}(G) = max {val(f) : f is a γ- labeling of G}$; while the minimum value of a γ-labeling of G is $val_{min}(G) = min {val(f) : f is a γ- labeling of G}$; The values $val_{max}(S_{p,q})$ and $val_{min}(S_{p,q})$ are determined for double stars $S_{p,q}$. We present characterizations of connected graphs G of order n for which $val_{min}(G) = n$ or $val_{min}(G) = n+1$.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Chartrand G.

2 VanderJagt D.

2 Zhang P.

1 Erwin D.

1 Lesniak L.

1 2008

1 2005

Wyniki wyszukiwania

Recognizable colorings of graphs

On γ-labelings of trees