Radio number of trees
| Autor: | Samir K. Vaidya, Sanming Zhou, Devsi Bantva |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Applied Mathematics 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology 05C78 05C15 01 natural sciences Upper and lower bounds Graph Combinatorics 010201 computation theory & mathematics FOS: Mathematics 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics Mathematics - Combinatorics Bound graph Combinatorics (math.CO) Mathematics |
| Popis: | A radio labeling of a graph $G$ is a mapping $f: V(G) \rightarrow \{0, 1, 2, \ldots\}$ such that $|f(u)-f(v)|\geq d + 1 - d(u,v)$ for every pair of distinct vertices $u, v$ of $G$, where $d$ is the diameter of $G$ and $d(u,v)$ the distance between $u$ and $v$ in $G$. The radio number of $G$ is the smallest integer $k$ such that $G$ has a radio labeling $f$ with $\max\{f(v) : v \in V(G)\} = k$. We give a necessary and sufficient condition for a lower bound on the radio number of trees to be achieved, two other sufficient conditions for the same bound to be achieved by a tree, and an upper bound on the radio number of trees. Using these, we determine the radio number for three families of trees. 19 pages, 7 figures. This is the final version accepted in Discrete Applied Mathematics |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|