Přejít k obsahu


Radio labelings of distance graphs

Citace: ČADA, R., EKSTEIN, J., HOLUB, P., TOGNI, O. Radio labelings of distance graphs. Discrete Applied Mathematics, 2013, roč. 161, č. 18, s. 2876-2884. ISSN: 0166-218X
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: Radio labelings of distance graphs
Rok vydání: 2013
Autoři: Doc. Ing. Roman Čada Ph.D. , RNDr. Jan Ekstein Ph.D. , RNDr. Přemysl Holub Ph.D. , Olivier Togni Ph.D.
Abstrakt CZ: Tématem tohoto článku je rádiové $k$-ohodnocení grafů motivované problémem přiřazovaní vysílacích kanálů. Rádiové $k$-ohodnocení souvislého grafu $G$ je přiřazení $c$ nezáporných celých čísel vrcholům grafu $G$ takové, že $$|c(x) - c(y)| >= k+1 - d(x,y),$$ pro každé dva různé vrcholy $x$ a $y$, kde $d(x,y)$ je vzdálenost mezi $x$ a $y$ v $G$. V tomto článku se studuje rádiové $k$-ohodnocení distančních grafů, tj. grafů s množinou $Z$ celých čísel jako množinou vrcholů grafu, v kterém dva vrcholy $i, j$ ze $Z$ jsou sousední právě tehdy, když $|i - j|$ je v $D$. Určíme dolní a horní meze pro rádiové $k$-ohodnocení distančních grafů s distančními množinami $D={1,2,..., t}$, $D={1,t}$ a $D={t-1,t}$ pro kladné celé číslo $t>1$.
Abstrakt EN: Motivated by the Channel Assignment Problem, we study radio $k$-labelings of graphs. A radio $k$-labeling of a connected graph $G$ is an assignment $c$ of non negative integers to the vertices of $G$ such that $$|c(x) - c(y)| >= k+1 - d(x,y),$$ for any two distinct vertices $x$ and $y$, where $d(x,y)$ is the distance between $x$ and $y$ in $G$. In this paper, we study radio $k$-labelings of distance graphs, i.e., graphs with the set $Z$ of integers as vertex set and in which two distinct vertices $i, j$ in $Z$ are adjacent if and only if $|i - j|$ is in $D$. We give some lower and upper bounds for radio $k$-labelings of distance graphs with distance sets $D={1,2,..., t}$, $D={1,t}$ and $D={t-1,t}$ for any positive integer $t>1$.
Klíčová slova

Zpět

Patička