Independent arcs of acyclic orientations of complete r-partite graphs
Journal
Discrete Mathematics
Journal Volume
309
Journal Issue
13
Pages
4280-4286
Date Issued
2009
Author(s)
Abstract
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 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. © 2009 Elsevier B.V.
Type
journal article