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

Author

Brendan McKay and Sean A. Irvine, Mar 17 2025

Keywords

• nonn
• more

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

• 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.