Acyclic orientations of complete bipartite graphs

✍ Scribed by Douglas B. West

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 216 KB
• Volume: 138
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)00222-5

✦ Synopsis

For a complete bipartite graph, the number of dependent edges in an acyclic orientation can be any integer from n-1 to e, where n and e are the number of vertices and edges in the graph.

Ke3,words: Bipartite graph; Acyclic orientation

Ill combinatorics we often ask whether an integer parameter can take on all values between its extremes. In this note we consider a question of this type for acyclic orientations of a graph. An acyclic orientation assigns an orientation to each edge of a simple graph so that no cycle is formed.

In an acyclic orientation H of a graph G, an edge is dependent if reversing its orientation creates a cycle -the other edges force its orientation. This definition is due to Paul Edelman [ll, who observed that the number f(H) of independent edges always satisfies n(G)--I <~f(H)<~e(G) (where n(G) and e(G) denote the number of vertices and edges of G), and that these extremes are achievable when G is bipartite. Lemma 1 below includes the lower bound, and orienting all edges from one partite set to the other achieves the upper bound. Edelman asked whether G being bipartite guarantees that every number from n(G)-1 to e(G) is achievable as f(H) for some acyclic orientation H of G . We call such a graph fully orientable. The Petersen graph, despite not being bipartite, is fully orientable, and we do not know of a triangle-free graph that is not fully orientable.

More generally, one can ask which values off(H) are achievable for an arbitrary G It is not possible to make all three edges of a triangle independent; hence e(G) may not be achievable. Indeed, the strongly connected components of an acyclic orientation of K, must be single vertices; hence every acyclic orientation of K, is a transitive orientation and has precisely n-1 independent edges.