Independent arcs of acyclic orientations of complete rr-partite graphs

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