A382180 Number of unlabeled connected graphs with n vertices which are squares.

1, 1, 1, 1, 2, 4, 13, 42, 206, 1310, 12622, 180700, 3925282

Offset

0,5

Comments

If G is an unlabeled finite simple graph, define its square S(G) to be the graph with the same vertices as G. The edges of S(G) are the edges of G together with an edge from vertex u to v whenever u and v are not adjacent in G but are joined by a path of length 2. [There is an obvious generalization to the square of a directed graph.- N. J. A. Sloane, Mar 24 2025]

The present definition, the number of unlabeled connected graphs with n vertices which are squares, implies "which are squares of connected graphs on n vertices", since if G is not connected, neither is its square. - N. J. A. Sloane, Mar 24 2025.

If the squares of two trees are isomorphic, then the trees themselves are isomorphic [Ross and Harary]. Thus the number of squares of trees is the same as the number of trees, A000055.

References

Frank Harary and Ian C. Ross, The Square of a Tree, Bell Labs Memorandum MM-59-122-2, May 16, 1959, 11 pages.

Links

Table of n, a(n) for n=0..12.

FindStat - The combinatorial statistics database, The square of a graph.

A. Mukhopadhyay, The Square Root of a Graph, J Comb. Th., 2, (1967), 290-295.

Ian C. Ross and Frank Harary, The square of a tree, The Bell System Technical J, 39, 3, May 1960.

Eric Weisstein's World of Mathematics, Graph Square.

Wikipedia, Graph power.

Crossrefs

Cf. A000055, A001349, A382194.

Inverse Euler transform of A382181.

Sequence in context: A284159 A050624 A135501 * A001548 A193057 A115600

Adjacent sequences: A382177 A382178 A382179 * A382181 A382182 A382183

Keyword

nonn,more

Author

Brendan McKay and Sean A. Irvine, Mar 17 2025

Status

approved