cp's OEIS Frontend

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

%I A382180 #23 Mar 24 2025 14:00:32
%S A382180 1,1,1,1,2,4,13,42,206,1310,12622,180700,3925282
%N A382180 Number of unlabeled connected graphs with n vertices which are squares.
%C A382180 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]
%C A382180 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.
%C A382180 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.
%D A382180 Frank Harary and Ian C. Ross, The Square of a Tree, Bell Labs Memorandum MM-59-122-2, May 16, 1959, 11 pages.
%H A382180 FindStat - The combinatorial statistics database, <a href="https://www.findstat.org/Mp00147">The square of a graph</a>.
%H A382180 A. Mukhopadhyay, <a href="https://doi.org/10.1016/S0021-9800(67)80030-9">The Square Root of a Graph</a>, J Comb. Th., 2, (1967), 290-295.
%H A382180 Ian C. Ross and Frank Harary, <a href="https://doi.org/10.1002/j.1538-7305.1960.tb03936.x">The square of a tree</a>, The Bell System Technical J, 39, 3, May 1960.
%H A382180 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GraphSquare.html">Graph Square</a>.
%H A382180 Wikipedia, <a href="https://en.wikipedia.org/wiki/Graph_power">Graph power</a>.
%Y A382180 Cf. A000055, A001349, A382194.
%Y A382180 Inverse Euler transform of A382181.
%K A382180 nonn,more
%O A382180 0,5
%A A382180 _Brendan McKay_ and _Sean A. Irvine_, Mar 17 2025