Radio Labelings of Distance Graphs

Roman Čada (1) , Jan Ekstein (1) , Premysl Holub (1) , Olivier Togni (2)

1 kma
2 Le2i - Laboratoire Electronique, Informatique et Image [UMR6306]

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)| \geq k+1 - d(x,y),$$ for any two vertices $x$ and $y$, $x\ne y$, where $d(x,y)$ is the distance between $x$ and $y$ in $G$. In this paper, we study radio 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| \in D$.

Mots clés: distance graph; graph labeling; radio k-labeling number; distance graph.

Domaines: Mathématique discrète [cs.DM]

Roman Čada, Jan Ekstein, Premysl Holub, Olivier Togni. Radio Labelings of Distance Graphs. Bordeaux Graph Workshop (BGW), Nov 2012, Bordeaux, France. ⟨hal-00787442⟩