On optimal acyclic orientations of a graph

Let G = (V, E) be a connected graph with a vertex set V and a prescribed set E of unordered pairs of vertices called edges. Let (G, R) denote the digraph obtained from graph G by an acyclic orientation R of its edges so that there is no directed cycle in (G, R). By η(G, R) we denote the number of pairs of non-adjacent vertices i, j in G such that there exists a directed path either from i to j or from j to i in ( G, R). Let η*(G) and η₀( G) denote the maximum and the minimum value of η(G, R ) over all acyclic orientations R, respectively. An orientation R of a graph G is said to be optimum if η(G, R) = η*(G) or η( G, R) = η₀(G). The problems of determining η*( G) and η₀(G) for an arbitrary graph are known to be NP-hard.; A linear algorithm is known to compute η*(G) when G is a tree, a connected graph containing no cycle. We consider the problems of determining η*(G) and η₀( G) and the associated orientations for unicyclic graphs, and determining extremal trees and unicyclic graphs. A unicyclic graph is the smallest connected graph containing a cycle, and therefore, not every orientation is acyclic as is the case with a tree. We present algorithms to determine optimal acyclic orientations for unicyclic graphs.; An (n, m) graph G—a graph with n vertices and m edges—is said to be extremal with respect to η*(G) if G maximizes (or minimizes) η*(G) over all (n, m) graphs. We determine extremal trees with respect to η*(G), η ₀(G), and η_e(G)—the expected value of η(G, R) over all R—and extremal unicyclic graphs with respect to η*(G) and η ₀(G). We conclude with some conjectures and directions for further research.