"The Complexity of Graphs and Digraphs"
THE COMPLEXITY OF GRAPHS AND DIGRAPHS Steven H. Bertz and Christina M. Zamfirescu Complexity Study Center, Mendham, NJ 07945 Department of Computer Science, Hunter College and Graduate Center, CUNY, New York, NY 10021 A graph is a collection of points together with a collection of unordered pairs of points, called edges. They can be used to model natural systems such as molecules, neural networks and ecosystems, e.g., in molecular graphs the points represent atoms and the edges represent bonds. In a directed graph or digraph the pairs of points are ordered, and they are called directed edges or arcs. Digraphs can also be used to model many real-world systems, from street maps to plans for sophisticated pharmaceutical syntheses. We have developed complexity measures for graphs and applied them to problems of molecular complexity, e.g., the change in complexity wrought by various chemical reactions. Our approach is to abstract the system under study as a graph or digraph and then characterize its complexity by using invariants, quantities that have the same values for isomorphic graphs. (Isomorphic graphs have the same adjacency matrix for some labelings of their points.) A subgraph of graph G is a graph that has all its points and lines in G. The most useful complexity measures for graphs that we have found are the total number of connected subgraphs, the number of kinds of connected subgraphs, the total number of biclique covers and the number of kinds of biclique covers. (For the definitions of these covers, see S.H. Bertz and C.M. Zamfirescu, MATCH–Communications in Mathematical and in Computer Chemistry 2000, 42, 39-70.) The total number of trees, graphs without cycles, and the number of kinds of trees are useful in some circumstances. We will describe the extension of these measures from graphs to digraphs and compare our results with those obtained by using the total walk count, a versatile complexity measure for graphs developed by Rücker and coworkers. We will also compare our approach to those based on information theory and algorithmic complexity.