Independent arcs of acyclic orientations of complete r-partite graphs

AbstractSuppose D is an acyclic orientation of a graph G. An arc of D is said to be independent if its reversal results in another acyclic orientation. Let i(D) denote the number of independent arcs in D, and let N(G)={i(D):D is an acyclic orientation of G}. Also, let imin(G) be the minimum of N(G) and imax(G) the maximum. While it is known that imin(G)=|V(G)|−1 for any connected graph G, the present paper determines imax(G) for complete r-partite graphs G. We then determine N(G) for any balanced complete r-partite graph G, showing that N(G) is not a set of consecutive integers. This answers a question raised by West. Finally, we give some complete r-partite graphs G whose N(G) is a set of consecutive integers