A382181 -id:A382181 - cp's OEIS frontend

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

Brendan McKay and Sean A. Irvine, Mar 17 2025

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.

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

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.

Cf. A000055, A001349, A382194.

Inverse Euler transform of A382181.

A382761 List of graphs that are squares, encoded as in A382754.

Original entry on oeis.org

0, 1, 2, 3, 8, 9, 15, 64, 65, 75, 76, 95, 127, 1024, 1025, 1043, 1044, 1079, 1207, 1208, 1247, 1279, 1535, 2047, 32768, 32769, 32803, 32804, 32871, 33383, 33384, 33424, 33455, 33519, 33689, 34543, 34687, 36863, 38639, 38640, 38673, 38711, 38719, 38783, 38911, 39423, 39935, 40959, 48638, 48639, 49151, 65535

Offset: 0

Pontus von Brömssen, Apr 05 2025

			As an irregular triangle, where row n >= 0 contains A382181(n) terms:
     0;
     1;
     2,    3;
     8,    9,   15;
    64,   65,   75,   76,   95,  127;
  1024, 1025, 1043, 1044, 1079, 1207, 1208, 1247, 1279, 1535, 2047;
  ...

Cf. A382181, A382194, A382754, A382762, A382763.

a(n) = A382754(A382762(n)).

A382762 List of graphs that are squares, encoded by their indices in A382754.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 7, 8, 9, 12, 13, 17, 18, 19, 20, 24, 25, 32, 39, 40, 47, 49, 51, 52, 53, 54, 59, 60, 70, 89, 90, 99, 107, 117, 127, 144, 160, 170, 171, 172, 177, 182, 186, 191, 193, 195, 201, 204, 205, 206, 207, 208

Offset: 0

Pontus von Brömssen, Apr 05 2025

			As an irregular triangle, where row n >= 0 contains A382181(n) terms:
   0;
   1;
   2,  3;
   4,  5,  7;
   8,  9, 12, 13, 17, 18;
  19, 20, 24, 25, 32, 39, 40, 47, 49, 51, 52;
  ...

Cf. A382181, A382194, A382754, A382761, A382764.

A381961 Number of connected graphs with n vertices which have a planar square.

Original entry on oeis.org

1, 1, 1, 2, 6, 6, 14, 25, 60, 124, 302, 696, 1745, 4300, 11042, 28362, 74483, 196539, 525521, 1413635, 3835932, 10468384

Offset: 0

Sean A. Irvine, Mar 18 2025

See A382180 for a definition of a square graph.

For a graph to have a planar square, it must also be planar itself. Further, the degree of every vertex must be <= 3 and the graph must have no 5-cycles.

Frank Harary, Richard M. Karp, and William T. Tutte, A Criterion for Planarity of the Square of a Graph, J. Comb. Th., 2, 1967, pp. 395-405.

Cf. A382180, A382181, A382284.

a(16)-a(20) from Brendan McKay, Mar 21 2025

a(21) from Sean A. Irvine, Mar 22 2025

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

A382761 List of graphs that are squares, encoded as in A382754.

Views

Author

Keywords

Examples

Crossrefs

Formula

A382762 List of graphs that are squares, encoded by their indices in A382754.

Views

Author

Keywords

Examples

Crossrefs

A381961 Number of connected graphs with n vertices which have a planar square.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions