An introduction to competition-reachability of a graph

ABSTRACT

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.

REFERENCES

• 1: C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
• 2: J. H. Conway, On Numbers and Games, Academic Press, New York (1976).
• 3: S. Even , A. Pnueli , A. Lempel, Permutation Graphs and Transitive Graphs, Journal of the ACM (JACM), v.19 n.3, p.400-410, July 1972 [doi>10.1145/321707.321710]
• 4: A. Finbow and B. Hartnell, A game related to covering by stars, Ars Combin., 16A (1983) 189--198.
• 5: A. Finbow and B. Hartnell, A characterization of parity graphs containing no cycles of order five or less, Ars Combin., 40 (1995) 227--234.
• 6: P. C. Gilmore and A. J. Hoffman, A characterization of comparability graphs and of interval graphs, Canad. J. Math. 16 (1964) 539--548.
• 7: S. Louis Hakimi , Edward F. Schmeichel , Neal E. Young, Orienting graphs to optimize reachability, Information Processing Letters, v.63 n.5, p.229-235, Sept. 15, 1997 [doi>10.1016/S0020-0190(97)00129-4]
• 8: J. B. Phillips and P. J. Slater, An introduction to graph competition independence and enclaveless parameters, Graph Theory Notes of New York XLI (2001) 37--41.
• 9: J. B. Phillips and P. J. Slater, Graph competition independence and enclaveless parameters, Congr. Numer., 154 (2002) 79--99.
• 10: H. E. Robbins, A Theorem on Graphs with an Application to a Problem of Traffic Control, Amer. Math. Monthly 46 (1939), pp. 281--283.
• 11: Suk Jai Seo , Ashok T. Amin, Algorithms for optimal orientations of a unicyclic graph, Proceedings of the 42nd annual Southeast regional conference, April 02-03, 2004, Huntsville, Alabama [doi>10.1145/986537.986589]
• 12: S. J. Seo and A. T. Amin, On extremal oriented trees. Congr. Numer. 152 (2001) 55--63.
• 13: P. J. Slater, Enclaveless sets and MK-systems, J. Res. Nat. Bur. Standards, 82 (1977) 197--202.
• 14: P. J. Slater, O. Chan, and C. Chen, On a characterization of comparability graphs. Ars Combin. 23 (1987) 67--79.
• 15: P. J. Slater and Y. Wang, The competitive-acquisition number of paths, Congr. Numer., to appear.
• 16: H. Wang and A. T. Amin, On Optimal Acyclic Orientations of a Graph, Congr. Numer., 137 (1999), pp. 121--128.

INDEX TERMS

General Terms:
Theory

Keywords:
competition parameters, orientations, reachability