2023/03/16 by Walter Carballosa, Carballosa, Walter, Jessica Khera +3
Computer Science · Engineering · Mathematics · #05B30 #05C20 #05C30 #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2303.09021
openalex publication_date 2023/03/16 · openalex created_date 2023/03/19 · openalex updated_date 2026/07/28
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 n1,n2,…,np via a vector with p symbols and length n=n1+n2+…+np 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 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 Kn1,…,np 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.