@article {IOPORT.05644944, author = {Chang, Gerard J. and Lin, Chen-Ying and Tong, Li-Da}, title = {Independent arcs of acyclic orientations of complete \$r\$-partite graphs.}, year = {2009}, journal = {Discrete Mathematics}, volume = {309}, number = {13}, issn = {0012-365X}, pages = {4280-4286}, publisher = {Elsevier Science B.V. (North-Holland), Amsterdam}, doi = {10.1016/j.disc.2009.01.002}, abstract = {Summary: 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.}, identifier = {05644944}, }