A382180 -id:A382180 - cp's OEIS frontend

A382194 List of connected graphs that are squares, encoded as in A076184.

0, 1, 7, 31, 63, 239, 255, 511, 1023, 3455, 3887, 3951, 3967, 4095, 7679, 7903, 7935, 8191, 16350, 16351, 16383, 32767, 104063, 104447, 106287, 106351, 111587, 111599, 112511, 112623, 112639, 127791, 127855, 127871, 128879, 128895, 129023, 131071, 237567

Offset: 1

Pontus von Brömssen, Mar 18 2025

Intersection of A382193 and A382195.

			As an irregular triangle, where row n >= 1 contains A382180(n) terms:
     0;
     1;
     7;
    31,   63;
   239,  255,  511, 1023;
  3455, 3887, 3951, 3967, 4095, 7679, 7903, 7935, 8191, 16350, 16351, 16383, 32767;
  ...
The diamond graph is connected and isomorphic to the square of the path graph on 4 vertices. The code of the diamond graph is 31, so 31 is a term.

Pontus von Brömssen, Table of n, a(n) for n = 1..1580 (graphs on up to 9 vertices)
Eric Weisstein's World of Mathematics, Graph Square.
Wikipedia, Graph power.

Cf. A076184, A382180, A382193, A382195, A382283.

A382181 Number of unlabeled graphs with n vertices (including disconnected graphs) which are squares.

Original entry on oeis.org

1, 1, 2, 3, 6, 11, 28, 77, 307, 1688, 14620, 197050, 4137271

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.

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

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.

Euler transform of A382180.

A382157 Number of n-node digraphs without loops, not necessarily connected, which are squares.

Original entry on oeis.org

1, 1, 3, 9, 46, 473, 13763, 1121383

Offset: 0

N. J. A. Sloane, Mar 24 2025, based on an email from Brendan McKay, Mar 18 2025

For the definition of the square of a graph, see A382180.

Cf. A382180. A382158, A382159.

A382158 Number of n-node oriented graphs (no loops or cycles of length 2), not necessarily connected, which are squares.

Original entry on oeis.org

1, 1, 2, 6, 26, 209, 4115, 206205, 24982238

Offset: 0

N. J. A. Sloane, Mar 24 2025, based on an email from Brendan McKay, Mar 18 2025

For the definition of the square of a graph, see A382180.

Cf. A382180. A382157, A382159.

A382159 Number of n-node acyclic digraphs, not necessarily connected, which are squares.

Original entry on oeis.org

1, 1, 2, 5, 17, 81, 600, 7182, 142425, 4664203, 4071974770

Offset: 0

N. J. A. Sloane, Mar 24 2025, based on an email from Brendan McKay, Mar 18 2025

For the definition of the square of a graph, see A382180.

Cf. A382180, A382157, A382158.

A382283 Number of square roots of connected square graphs in the order listed in A382194.

Original entry on oeis.org

1, 1, 2, 1, 5, 1, 2, 3, 15, 1, 1, 2, 3, 4, 1, 3, 3, 15, 1, 1, 17, 60, 1, 2, 1, 2, 1, 1, 1, 1, 4, 2, 3, 2, 4, 11, 10, 11, 2, 1, 5, 3, 3, 6, 9, 8, 6, 1, 1, 19, 51, 3, 21, 1, 1, 3, 21, 2, 3, 113, 1, 11, 127, 374, 1, 1, 2, 3, 4, 1, 1, 2, 3, 4, 1, 1, 2, 1, 1, 1, 2

Offset: 1

Pontus von Brömssen, Mar 22 2025

A382194 lists all connected graphs that are squares, encoded as in A076184. a(n) is the number of unlabeled graphs whose squares are isomorphic to the n-th graph in A382194.

			As an irregular triangle, where row n >= 1 contains A382180(n) terms:
  1;
  1;
  2;
  1, 5;
  1, 2, 3, 15;
  1, 1, 2,  3, 4, 1, 3, 3, 15, 1, 1, 17, 60;
  ...
The last term on row n equals A241706(n)+1, the number of graphs whose square is the complete graph on n vertices.

Pontus von Brömssen, Table of n, a(n) for n = 1..1580 (for graphs on up to 9 vertices)
Eric Weisstein's World of Mathematics, Graph Square.
Wikipedia, Graph power.

Cf. A076184, A241706, A382180, A382194.

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

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

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 7, 13, 31, 60, 146, 320, 787, 1864, 4654, 11526, 29318, 74632, 192868, 500487, 1310826

Offset: 0

Brendan McKay and Sean A. Irvine, Mar 20 2025

See A382180 for a definition of a square graph.

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. A381961, A382180.

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

cp's OEIS Frontend

A382194 List of connected graphs that are squares, encoded as in A076184.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A382181 Number of unlabeled graphs with n vertices (including disconnected graphs) which are squares.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A382157 Number of n-node digraphs without loops, not necessarily connected, which are squares.

Views

Author

Keywords

Comments

Crossrefs

A382158 Number of n-node oriented graphs (no loops or cycles of length 2), not necessarily connected, which are squares.

Views

Author

Keywords

Comments

Crossrefs

A382159 Number of n-node acyclic digraphs, not necessarily connected, which are squares.

Views

Author

Keywords

Comments

Crossrefs

A382283 Number of square roots of connected square graphs in the order listed in A382194.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions