MIT Combinatorics Seminar

Cartesian product of graphs and arithmetic product of species

Ji Li  (Brandeis University)

Friday, March 09, 2007    4:15 pm    Room 2-136


Sabidussi showed that any connected graph can be uniquely decomposed into prime factores up to isomorphism with respect to the Cartesian product of graphs. This gives a free commutative monoid structure on the set of unlabeled connected graphs, generated by the set of unlabeled prime graphs. As a consequence of Sabidussi's theorem, we count prime graphs using Dirichlet series. On the other hand, as it turns out, the prime graphs can be enumerated in terms of connected graphs using species theory under the notion arithematic product of species defined by Maria and Mendez. We shall take a quick look at how that could be done.