MIT Combinatorics Seminar
Cartesian product of graphs and arithmetic product of species
Ji Li
(Brandeis University)
Friday, March 09, 2007
4:15 pm Room 2136
ABSTRACT

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.


