A Lower Bound for the Radio Number of Graphs
| Autor: | Devsi Bantva |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Algorithms and Discrete Applied Mathematics ISBN: 9783030115081 CALDAM |
| DOI: | 10.1007/978-3-030-11509-8_14 |
| Popis: | A radio labeling of a graph G is a mapping \(\varphi : V(G) \rightarrow \{0, 1, 2,\ldots \}\) such that \(|\varphi (u)-\varphi (v)|\ge \mathrm{diam}(G) + 1 - d(u,v)\) for every pair of distinct vertices u, v of G, where \(\mathrm{diam}(G)\) and d(u, v) are the diameter of G and distance between u and v in G, respectively. The radio number \(\mathrm{rn}(G)\) of G is the smallest number k such that G has radio labeling with \(\max \{\varphi (v):v \in V(G)\} = k\). In this paper, we slightly improve the lower bound for the radio number of graphs given by Das et al. in [5] and, give necessary and sufficient condition to achieve the lower bound. Using this result, we determine the radio number for cartesian product of paths \(P_{n}\) and the Peterson graph P. We give a short proof for the radio number of cartesian product of paths \(P_{n}\) and complete graphs \(K_{m}\) given by Kim et al. in [6]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|