Diameter two orientability of mixed graphs
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_ | 1866911996323037184 |
|---|---|
| author | Li, Hengzhe Ding, Zhiwei Liu, Jianbing Lai, Hong-Jian |
| author_facet | Li, Hengzhe Ding, Zhiwei Liu, Jianbing Lai, Hong-Jian |
| contents | In 1967, Katona and Szemerédi showed that no undirected graph with $n$ vertices and fewer than $\frac{n}{2}\log_2\frac{n}{2}$ edges admits an orientation of diameter two. In 1978, Chvátal and Thomassen revealed the complexity of determining whether an undirected graph can be oriented to achieve a diameter of two, proving it to be NP-complete. This breakthrough has sparked ongoing interest in identifying sufficient conditions for graphs to be oriented with the smallest possible diameter of two -- critical for optimizing communication and network flow in larger structures. In 2019, Czabarka, Dankelmann, and Székely significantly advanced this field by establishing that the minimum degree threshold for achieving such an orientation in undirected graphs of order $n$ is $\frac{n}{2} + Θ(\ln n)$. In this paper, we extend this foundational result by determining the minimum degree threshold necessary for realizing an orientation with diameter two in mixed graphs, which contain both undirected and directed edges. Mixed graphs offer a versatile framework, representing an intermediate stage in the orientation process, making our findings a substantial generalization of previous results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_10809 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Diameter two orientability of mixed graphs Li, Hengzhe Ding, Zhiwei Liu, Jianbing Lai, Hong-Jian Combinatorics 05C07, 05C12, 05C20 In 1967, Katona and Szemerédi showed that no undirected graph with $n$ vertices and fewer than $\frac{n}{2}\log_2\frac{n}{2}$ edges admits an orientation of diameter two. In 1978, Chvátal and Thomassen revealed the complexity of determining whether an undirected graph can be oriented to achieve a diameter of two, proving it to be NP-complete. This breakthrough has sparked ongoing interest in identifying sufficient conditions for graphs to be oriented with the smallest possible diameter of two -- critical for optimizing communication and network flow in larger structures. In 2019, Czabarka, Dankelmann, and Székely significantly advanced this field by establishing that the minimum degree threshold for achieving such an orientation in undirected graphs of order $n$ is $\frac{n}{2} + Θ(\ln n)$. In this paper, we extend this foundational result by determining the minimum degree threshold necessary for realizing an orientation with diameter two in mixed graphs, which contain both undirected and directed edges. Mixed graphs offer a versatile framework, representing an intermediate stage in the orientation process, making our findings a substantial generalization of previous results. |
| title | Diameter two orientability of mixed graphs |
| topic | Combinatorics 05C07, 05C12, 05C20 |
| url | https://arxiv.org/abs/2408.10809 |