Encoding acyclic orientation of complete multipartite graphs

arXiv2303.09021MaRDI QIDQ6429751FDOQ6429751

Authors: Walter Carballosa, Jessica Khera, Francisco Reyes 

Publication date: 15 March 2023

Abstract: In this work we study the acyclic orientations of complete multipartite graphs. We obtain an encoding of the acyclic orientations of the complete $p$-partite graph with size of its parts $n:=n_1,n_2,ldots,n_p$ via a vector with $p$ symbols and length $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 $mathcalO(n)$. Besides, obtained codification of the acyclic orientations allows us to count the number of non-isomorphic acyclic orientations of the complete multipartite graphs. Furthermore, we obtain a closed formula for non-isomorphic acyclic orientations of the complete multipartite graphs with a directed spanning tree. In addition, we obtain a closed formula for the ordinary generating functions for the number of strings in the alphabet $s_1,s_2,ldots,s_p$ with $k_1$ characters $s_1$, $k_2$ characters $s_2$, and so on with $k_p$ characters $s_p$ such that no two consecutive characters are the same. Finally, we obtain a closed formula for the number of acyclic orientation of a complete multipartite graph $K_{n_1,ldots,n_p}$ with labelled vertices.

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30)

This page was built for publication: Encoding acyclic orientation of complete multipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6429751)