Graph complexity (Q1823693)

The authors study (Boolean) complexity of graphs, in analogy to complexity of Boolean functions. The idea is the following. Let V be a set of vertices. A graph on V is a subset of \(V\times V\) and a set of graphs is a subset of P(V\(\times V)\) (P denotes the powerset operation). Let B be a set of (Boolean) set operations and let G be a set of graphs; graphs in G are called generators and B is called the basis. Now, given a graph H (on V) the question is how difficult it is to express H in terms of the G and B. The authors consider two complexity measures, formula size and circuit size with respect to two classes of generators, star graphs and complete bipartite graphs. They prove some lower bounds on the complexity of some explicitly given graphs.