Cographs as free algebra
A cograph is a graph formed from single vertices by disjoint union and complement operations, but I think it makes the theory a little cleaner to think of them as generated instead by the following set of three operations:
- vertex(): takes no arguments and returns a single vertex
- union(G,H): takes two graphs as arguments and returns their disjoint union
- join(G,H): takes two graphs as arguments and adds all possible edges connecting the two
The join of G and H equals complement(union(complement(G),complement(H))). Both union and join are commutative and associative.
Every cograph can be represented as a cotree: a tree in which each leaf corresponds to a graph vertex, each internal vertex is labeled with a 0 or 1, and two vertices are connected by an edge if their least common ancestor is labeled by a 1.
If we interpret leaves as vertex operations, 0 nodes as (sequences of) union operations, and 1 nodes as (sequences of) join operations, we get a formula that, when evaluated, gives us our graph. The tree is uniquely defined if we require internal nodes to have two or more children and to alternate between 0's and 1's along any path to the root; therefore, different formulae (up to commutativity and associativity) will give different cographs. Or, in other words, the cographs represent elements of the free algebra generated by one 0-ary operation and two commutative associative operations.
Various pieces of useful information about a cograph may be obtained by mapping this free algebra to other algebras: translating the graph into a formula involving the vertex, union, and join operations, replacing these three operations by some three other operations in some other algebra, and then evaluating the replaced formula. It is only required that the new union and join operations be commutative and associative operations on objects given by the vertex operation.
| Quantity | Replacement for vertex | Replacement for union | Replacement for join |
|---|---|---|---|
| Size of maximum independent set | 1 | + | max |
| Size of maximum clique | 1 | max | + |
| Number of maximal independent sets | 1 | × | + |
| Number of maximal cliques | 1 | + | × |
| Number of independent sets | 2 | × | a + b − 1 |
| Number of cliques | 2 | a + b − 1 | × |
| Size of smallest maximal independent set | 1 | + | min |
| Size of smallest maximal clique | 1 | min | + |
| Generating function for number of independent sets of size k | x + 1 | × | p(x) + q(x) − 1 |
| Generating function for number of k-cliques | x + 1 | p(x) + q(x) − 1 | × |
| Number of k-colorings, for k = 0,1,2,... | Infinite vector (0,1,2,...) | Coordinatewise product | Vector convolution |
The last example, in particular, shows that we can calculate the chromatic polynomial efficiently (by computing a truncation of the infinite vector and interpolating), a difficult task for more general classes of graphs. The existence of an efficient chromatic polynomial algorithm for cographs was briefly noted by Giménez, Hliněný, and Noy, in a paper about computing even more difficult invariants for these graphs.
Comments:
2008-05-14T13:22:05Z
Thanks for the feedback!
2008-05-14T18:49:11Z
Are there any concrete applications of this. Are Cographs naturally encountered in practice for real problems.
2008-05-14T18:51:56Z
Series parallel graphs are certainly encountered in circuit design, and cographs encode reachability in series parallel graphs. Whether the quantities one can compute in this way encode information of interest in designing tests for circuits, I'm less sure, but I wouldn't be surprised.
2008-05-15T03:59:09Z
Graphs can be considered simplicial complexes, by assuming that every clique is filled with a simplex of appropriate dimension. In this interpretation, the join of graphs corresponds to the join of simplicial complexes.
Girard used these graphs/simplicial complexes, under the name "coherence spaces", to provide semantics for linear logic. If I understand correctly, Join and Union correspond to a pair of the linear logic connectives.
In this world, there was a third operation to combine two graphs. Points in the combined graph correspond to pairs (g, h) of points in the original graphs G and H. There is an edge from (g, h) to (g', h') iff there is an edge from g to g' and h to h'. This is called at mathworld "graph categorical product".
2008-05-15T07:06:49Z
Interesting. If you fill each clique with a hypercube instead of with a simplex, you get a cubing, the skeleton of which is a median graph having a vertex for each simplex. Or, it's the same as the inclusion lattice of the simplicial complex...
The same product you describe is called the tensor product of graphs on Wikipedia, which has a more detailed article than Mathworld's. Now I'm wondering what class of graphs you get by combining these three operations. I guess I'll have to look up the Girard paper.
2008-05-15T10:23:24Z
I'm sorry, I should have provided a reference. I was reading Chapter 8 and Appendix A of "Proofs and Types".