On Graph Complexity

A circuit complexity of a graph is the minimum number of union and intersection operations needed to obtain the whole set of its edges starting from stars. Our main motivation to study this measure of graphs is that it is related to the circuit complexity of boolean functions. We prove some lower bounds to the circuit complexity of explicitly given graphs. In particular, we use the graph theoretic frame to prove that some ex-plicit subsets of GF (2)n cannot be covered by fewer than 2 (n) ane subspaces of GF (2)n. We conclude with several graph-theoretic problems whose solution would have intriguing consequences in computational complexity