Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2303.09021 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916722956566528 |
|---|---|
| author | Carballosa, Walter Khera, Jessica Reyes, Francisco |
| author_facet | Carballosa, Walter Khera, Jessica Reyes, Francisco |
| contents | In this work we study the acyclic orientations of graphs. We obtain an encoding of the acyclic orientations of the complete $p$-partite graph with size of its parts $n_1,n_2,\ldots,n_p$ via a vector with $p$ symbols and length $n=n_1+n_2+\ldots+n_p$ when the parts are fixed but not the vertices in each part. We also give a recursive way to construct all acyclic orientations of a complete multipartite graph, this construction can be done by computer easily in order $\mathcal{O}(n)$. Furthermore, we obtain a closed formula for non-isomorphic acyclic orientations of both the complete multipartite graphs and the complete multipartite graphs with a directed spanning tree. Moreover, we obtain a closed formula for the number of acyclic orientations of a complete multipartite graph $K_{n_1,\ldots,n_p}$ with labelled vertices. Finally, we obtain a way encode all acyclic orientations of an arbitrary graph as a permutation code. Using the codification mentioned above we obtain sharp upper and lower bounds of the number of acyclic orientations of a graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_09021 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Encoding and Enumerating Acyclic Orientations of Graphs Carballosa, Walter Khera, Jessica Reyes, Francisco Combinatorics 05B30, 05C20, 05C30 In this work we study the acyclic orientations of graphs. We obtain an encoding of the acyclic orientations of the complete $p$-partite graph with size of its parts $n_1,n_2,\ldots,n_p$ via a vector with $p$ symbols and length $n=n_1+n_2+\ldots+n_p$ when the parts are fixed but not the vertices in each part. We also give a recursive way to construct all acyclic orientations of a complete multipartite graph, this construction can be done by computer easily in order $\mathcal{O}(n)$. Furthermore, we obtain a closed formula for non-isomorphic acyclic orientations of both the complete multipartite graphs and the complete multipartite graphs with a directed spanning tree. Moreover, we obtain a closed formula for the number of acyclic orientations of a complete multipartite graph $K_{n_1,\ldots,n_p}$ with labelled vertices. Finally, we obtain a way encode all acyclic orientations of an arbitrary graph as a permutation code. Using the codification mentioned above we obtain sharp upper and lower bounds of the number of acyclic orientations of a graph. |
| title | Encoding and Enumerating Acyclic Orientations of Graphs |
| topic | Combinatorics 05B30, 05C20, 05C30 |
| url | https://arxiv.org/abs/2303.09021 |