Maximal Line Digraphs
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_ | 1866916283391410176 |
|---|---|
| author | Japhet, Quentin Watel, Dimitri Barth, Dominique Weisser, Marc-Antoine |
| author_facet | Japhet, Quentin Watel, Dimitri Barth, Dominique Weisser, Marc-Antoine |
| contents | A line digraph $L(G) = (A, E)$ is the digraph constructed from the digraph $G = (V, A)$ such that there is an arc $(a,b)$ in $L(G)$ if the terminal node of $a$ in $G$ is the initial node of $b$. The maximum number of arcs in a line digraph with $m$ nodes is $(m/2)^2 + (m/2)$ if $m$ is even, and $((m - 1)/2)^2 + m - 1$ otherwise. For $m \geq 7$, there is only one line digraph with as many arcs if $m$ is even, and if $m$ is odd, there are two line digraphs, each being the transpose of the other. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_05141 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Maximal Line Digraphs Japhet, Quentin Watel, Dimitri Barth, Dominique Weisser, Marc-Antoine Discrete Mathematics Computational Complexity A line digraph $L(G) = (A, E)$ is the digraph constructed from the digraph $G = (V, A)$ such that there is an arc $(a,b)$ in $L(G)$ if the terminal node of $a$ in $G$ is the initial node of $b$. The maximum number of arcs in a line digraph with $m$ nodes is $(m/2)^2 + (m/2)$ if $m$ is even, and $((m - 1)/2)^2 + m - 1$ otherwise. For $m \geq 7$, there is only one line digraph with as many arcs if $m$ is even, and if $m$ is odd, there are two line digraphs, each being the transpose of the other. |
| title | Maximal Line Digraphs |
| topic | Discrete Mathematics Computational Complexity |
| url | https://arxiv.org/abs/2406.05141 |