A Note on Improved bounds for the Oriented Radius of Mixed Multigraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917710018904064 |
|---|---|
| author | Li, Hengzhe Ding, Zhiwei Liu, Jianbing Gao, Yanhong Zhao, Shuli |
| author_facet | Li, Hengzhe Ding, Zhiwei Liu, Jianbing Gao, Yanhong Zhao, Shuli |
| contents | For a positive integer $r$, let $f(r)$ denote the smallest number such that any 2-edge connected mixed graph with radius $r$ has an oriented radius of at most $f(r)$. Recently, Babu, Benson, and Rajendraprasad significantly improved the upper bound of $f(r)$ by establishing that $f(r) \leq 1.5r^2 + r + 1$, see [Improved bounds for the oriented radius of mixed multigraphs, J. Graph Theory, 103 (2023), 674-689]. Additionally, they demonstrated that if each edge of a graph $G$ is contained within a cycle of length at most $η$, then the oriented radius of $G$ is at most $1.5rη$. The authors' results were derived through Observation 1, which served as the foundation for the development of Algorithm ORIENTOUT and Algorithm ORIENTIN. By integrating these algorithms, they obtained the improved bounds. However, an error has been identified in Observation 1, necessitating revisions to Algorithm ORIENTOUT and Algorithm ORIENTIN. In this note, we address the error and propose the necessary modifications to both algorithms, thereby ensuring the correctness of the conclusions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_01612 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Note on Improved bounds for the Oriented Radius of Mixed Multigraphs Li, Hengzhe Ding, Zhiwei Liu, Jianbing Gao, Yanhong Zhao, Shuli Combinatorics 05C12, 05C40 For a positive integer $r$, let $f(r)$ denote the smallest number such that any 2-edge connected mixed graph with radius $r$ has an oriented radius of at most $f(r)$. Recently, Babu, Benson, and Rajendraprasad significantly improved the upper bound of $f(r)$ by establishing that $f(r) \leq 1.5r^2 + r + 1$, see [Improved bounds for the oriented radius of mixed multigraphs, J. Graph Theory, 103 (2023), 674-689]. Additionally, they demonstrated that if each edge of a graph $G$ is contained within a cycle of length at most $η$, then the oriented radius of $G$ is at most $1.5rη$. The authors' results were derived through Observation 1, which served as the foundation for the development of Algorithm ORIENTOUT and Algorithm ORIENTIN. By integrating these algorithms, they obtained the improved bounds. However, an error has been identified in Observation 1, necessitating revisions to Algorithm ORIENTOUT and Algorithm ORIENTIN. In this note, we address the error and propose the necessary modifications to both algorithms, thereby ensuring the correctness of the conclusions. |
| title | A Note on Improved bounds for the Oriented Radius of Mixed Multigraphs |
| topic | Combinatorics 05C12, 05C40 |
| url | https://arxiv.org/abs/2407.01612 |