Construction of large graphs with no optimal surjective L(2,1)-labelings

KRÁĽ, Daniel; R SKREKOVSKI a M TANCER. Construction of large graphs with no optimal surjective L(2,1)-labelings. SIAM Journal on Discrete Mathematics. Philadelphia: SIAM, 2006, roč. 20, č. 2, s. 536-543. ISSN 0895-4801. Dostupné z: https://doi.org/10.1137/050623061.

Základní údaje

Originální název

Construction of large graphs with no optimal surjective L(2,1)-labelings

Autoři

KRÁĽ, Daniel; R SKREKOVSKI a M TANCER

Vydání

SIAM Journal on Discrete Mathematics, Philadelphia, SIAM, 2006, 0895-4801

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.518

Označené pro přenos do RIV

Ne

DOI

https://doi.org/10.1137/050623061

UT WoS

000238838200017

Klíčová slova anglicky

channel assignment problem; graph labeling with distance conditions

---

Anotace

V originále

An L(2, 1)-labeling of a graph G is a mapping c : V (G) --> {0,..., K} such that the labels of two adjacent vertices differ by at least two and the labels of vertices at distance two differ by at least one. A hole of c is an integer h. {0,..., K} that is not used as a label for any vertex of G. The smallest integer K for which an L(2, 1)-labeling of G exists is denoted by lambda(G). The minimum number of holes in an optimal labeling, i.e., a labeling with K = lambda(G), is denoted by rho(G). Georges and Mauro [SIAM J. Discrete Math., 19 ( 2005), pp. 208 - 223] showed that rho(G) <= Delta, where Delta is the maximum degree of G, and conjectured that if.( G) =. and G is connected, then the order of G is at most Delta(Delta+1). We disprove this conjecture by constructing graphs G with rho(G) = Delta and order [(Delta+1)(2)/4] (Delta+ 1) approximate to Delta(3)/4.