0xDE (![[info]](http://l-stat.livejournal.com/img/userinfo.gif){kind=small} 11011110) wrote,@ 2008-05-13 22:41:00 |
|
| Entry tags: | graph theory |
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),complemen
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.
