cp's OEIS Frontend

A "peerless" tree is an unlabeled, unrooted tree (as in A000055) with the property that if two nodes are joined by an edge then these nodes have different degrees.

Victor S. Miller reports that this sequence was first proposed on Project Euler.

Comment from Brendan McKay, May 01 2025 (Start)

The enumeration could be extended by the following argument.

If the tree has a unique centroid (not center!) then removing the centroid gives rooted subtrees of size less than n/2. If there are two centroids, they are adjacent and removing that edge gives two rooted subtrees with exactly n/2 vertices.

Start by making all rooted trees up to n/2 vertices which have no adjacent vertices of the same degree, not counting adjacencies of the root. Then classify them according to which degrees the root can be increased to without violating this condition for edges adjacent to the root.

With this information the counts for n vertices can be reconstructed. In this way getting up past 60 vertices should be possible. (End)

This sequence forms the left-most column of A383448.

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

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

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

See A382180 for a definition of a square graph.

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.

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.

A chordal bipartite graph is a bipartite graph with no induced cycles longer than 4-cycles. Note that this is not the same as a bipartite graph which is chordal, as that would exclude all cycles.