A129581 Number of labeled prime graphs with respect to the Cartesian multiplication of graphs.
1, 1, 4, 35, 728, 26464, 1866256, 251518352, 66296210432, 34496477587456, 35641657548953344, 73354596197458024448, 301272202649664088951808, 2471648811030427594714599424, 40527680937730480229320939012096
Offset: 1
Examples
Almost all connected graphs are prime graphs with respect to Cartesian product of graphs. So instead of giving an example of prime graph, we give here an example of a connected nonprime graph on vertices {1,2,3,4}:
1 --- 4
| ... |
2 --- 3
The above graph is not prime since it is the Cartesian product of two line graphs of order 2.
Links
- Ji Li, Prime graphs and exponential Composition of Species, arXiv:0705.0038
- Ji Li, Prime graphs and exponential composition of species, J. Combin. Theory A 115 (2008) 1374-1401
Formula
Let D(P) be the exponential Dirichlet generating series for the species of prime graphs and let D(C) be the exponential Dirichlet generating series for the species of connected graphs. We have D(P)=log D(C)