Radio gracefulness of Moore graphs and beyond
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908571109687296 |
|---|---|
| author | Cao, An Dawkins, Aleyah Hutchins, Julian Luce, Orlando |
| author_facet | Cao, An Dawkins, Aleyah Hutchins, Julian Luce, Orlando |
| contents | The study of radio graceful labelings is motivated by modeling efficient frequency assignment to radio towers, cellular towers, and satellite networks. For a simple, connected graph $G = (V(G), E(G))$, a radio labeling is a mapping $f: V(G) \rightarrow \mathbb{Z}^+$ satisfying (for any distinct vertices $u,v$) $$|f(u)-f(v)| + d(u,v) \geq diam(G)+1,$$ where $d(u,v)$ is the distance between $u$ and $v$ in $G$ and $diam(G)$ is the diameter of $G$. A graph is radio graceful if there is a radio labeling such that $f(V(G)) = \{1, \dots, |V(G)|\}$. In this paper, we determine the radio gracefulness of low-diameter graphs with connections to high-performance computing, including Moore graphs, bipartite Moore graphs, and approximate Moore graphs like $(r,g)-$cages, Erdős-Rényi polarity graphs, and McKay-Miller-Širáň graphs. We prove a new necessary and sufficient condition for radio graceful bipartite graphs with diameter $3$. We compute the radio number of $(r,g)-$cages arising from generalized $n-$gons. Additionally, we determine Erdős-Rényi polarity graphs and McKay-Miller-Širáň graphs are radio graceful. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_00228 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Radio gracefulness of Moore graphs and beyond Cao, An Dawkins, Aleyah Hutchins, Julian Luce, Orlando Combinatorics 05C78 The study of radio graceful labelings is motivated by modeling efficient frequency assignment to radio towers, cellular towers, and satellite networks. For a simple, connected graph $G = (V(G), E(G))$, a radio labeling is a mapping $f: V(G) \rightarrow \mathbb{Z}^+$ satisfying (for any distinct vertices $u,v$) $$|f(u)-f(v)| + d(u,v) \geq diam(G)+1,$$ where $d(u,v)$ is the distance between $u$ and $v$ in $G$ and $diam(G)$ is the diameter of $G$. A graph is radio graceful if there is a radio labeling such that $f(V(G)) = \{1, \dots, |V(G)|\}$. In this paper, we determine the radio gracefulness of low-diameter graphs with connections to high-performance computing, including Moore graphs, bipartite Moore graphs, and approximate Moore graphs like $(r,g)-$cages, Erdős-Rényi polarity graphs, and McKay-Miller-Širáň graphs. We prove a new necessary and sufficient condition for radio graceful bipartite graphs with diameter $3$. We compute the radio number of $(r,g)-$cages arising from generalized $n-$gons. Additionally, we determine Erdős-Rényi polarity graphs and McKay-Miller-Širáň graphs are radio graceful. |
| title | Radio gracefulness of Moore graphs and beyond |
| topic | Combinatorics 05C78 |
| url | https://arxiv.org/abs/2510.00228 |