On Link-irregular Digraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915692719112192 |
|---|---|
| author | Bastien, Alexander Khormali, Omid |
| author_facet | Bastien, Alexander Khormali, Omid |
| contents | We extend the study of link-irregular graphs to directed graphs (digraphs), where a digraph is link-irregular if no two vertices have isomorphic directed links. We establish that link-irregular digraphs exist on $n$ vertices if and only if $n \geq 5$, and prove that their underlying graphs must contain 3-cycles. We conjecture that link-irregular tournaments exist if and only if $n \geq 6$, providing explicit constructions for $n \leq 8$ and computational verification for $n \leq 100$. We derive lower bounds on the minimum degree and outdegree required for link-irregularity, establish that almost all link-irregular digraphs are nonplanar, and prove that any link-irregular orientable graph admits a link-irregular labeling. Additionally, we construct explicit examples of link-irregular digraphs with constant outdegree and regular tournaments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_20494 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Link-irregular Digraphs Bastien, Alexander Khormali, Omid Combinatorics 05C20, 05C35, 05C78 We extend the study of link-irregular graphs to directed graphs (digraphs), where a digraph is link-irregular if no two vertices have isomorphic directed links. We establish that link-irregular digraphs exist on $n$ vertices if and only if $n \geq 5$, and prove that their underlying graphs must contain 3-cycles. We conjecture that link-irregular tournaments exist if and only if $n \geq 6$, providing explicit constructions for $n \leq 8$ and computational verification for $n \leq 100$. We derive lower bounds on the minimum degree and outdegree required for link-irregularity, establish that almost all link-irregular digraphs are nonplanar, and prove that any link-irregular orientable graph admits a link-irregular labeling. Additionally, we construct explicit examples of link-irregular digraphs with constant outdegree and regular tournaments. |
| title | On Link-irregular Digraphs |
| topic | Combinatorics 05C20, 05C35, 05C78 |
| url | https://arxiv.org/abs/2512.20494 |