An introduction to competition-reachability of a graph
Suk J. Seo, Peter J. Slater · 2005
Let G be an undirected graph. A directed graph D obtained from G by assigning a direction to each edge in G is called an oriented graph. The reachability r(D) of a directed graph D is the number of ordered pairs of distinct vertices (x, y) with a directed path from x to y. Consider a graphical game associated with a graph G=(V, E) involving two players (maximizer and minimizer) who alternately select edges and orient them. The maximizer attempts to maximize the reachability, while the minimizer attempts to minimize the reachability, of the resulting digraph. If both players play optimally, then the reachability is fixed. Parameters that assign a value to each graph in this manner are called competitive parameters. We determine the competitive-reachability for special classes of graphs.