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,3

Links

Table of n, a(n) for n=1..15.

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)

Example

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.

Crossrefs

Cf. This is the logarithmic of A001187. Unlabeled prime graphs is given by A129582.

Sequence in context: A346802 A351730 A125798 * A356544 A120055 A192012

Adjacent sequences: A129578 A129579 A129580 * A129582 A129583 A129584

Keyword

easy,nonn

Author

Ji Li (vieplivee(AT)hotmail.com), May 04 2007

Status

approved