| Abstrakt: |
An L(2, 1)-labeling of a graph G = (V, E) is a function f from the vertex set V to the set of all non-negative integers such that | f (x) − f (y)| ≥ 2 if dG(x, y) = 1 and | f (x) − f (y)| ≥ 1 if dG(x, y) = 2. The span of f is the difference between the largest and the smallest label used by f. The L(2, 1)-labeling number of a graph G, denoted by λ (G), is the minimum span over all L(2, 1)-labelings of G. The Mycielski's construction is a well-known construction that transform a k-chromatic graph G into (k+1)-chromatic graph M(G) called the Mycielskian of G which has the same clique number as G. In this paper, we study the L(2, 1)-labeling of the Mycielskian of some graphs. First we give a formula for λ (M(G)) for graphs of diameter at most two, then we give the exact value for λ (M(G)) and provide examples of optimal L(2, 1)-labelings for M(G) when G is the Petersen graph, star, fan, wheel or friendship graph. Then we study the L(2, 1)-labeling number of the Mycielskian of some tree graphs and we give the exact number for the Mycielskian of spider tree and centipede graphs. [ABSTRACT FROM AUTHOR] |
