Independent arcs of acyclic orientations of complete -partite graphs

Suppose 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 i min ( G ) be the minimum of N ( G ) and i max ( G ) the maximum. While it is known that i min ( G ) = | V ( G ) | − 1 for any connected graph G , the present paper determines i max ( 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.