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

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

Offset: 0

Author

Sean A. Irvine, Mar 18 2025

Keywords

• nonn
• hard
• more

Comments

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.

Links

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

Crossrefs

Cf. A382180, A382181, A382284.

Extensions

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

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