A371514 a(n) is the number of subsets of [floor(n/2)]* that are realizable by a graph G with n vertices.

1, 2, 2, 4, 4, 7, 7, 11, 12, 19

Offset

1,2

Comments

A tree T with n vertices is bipartite. We write T=(X,Y) where the vertices of T in the first part are X, of order |X|=k, and the vertices in the second part are Y, of order |Y|=n-k. We arrange X and Y so that |X|<=|Y|. Then T has type (k,n-k), and we denote it by T_k. Let [floor(n/2)]*={(1,n-1),(2,n-2),...,(floor(n/2),ceiling(n/2))} be the set of all possible types for a graph with n vertices. For a connected graph G with n vertices, we define D(G)={(k,n-k)|G has a spanning tree T_k of type (k,n-k)}. For any subset S in [floor(n/2)]*, we say that S is realizable if there exists a graph G with n vertices and D(G)=S.

Realizable subsets will be featured in an upcoming article by Jayasooriya, McSorley, and Schuerger.

Links

Table of n, a(n) for n=1..10.

Example

For n=6, a(6)=7. The set [floor(n/2)]* = {(1,5),(2,4),(3,3)}. So there are 8 subsets of [floor(n/2)]*. Out of those 8, the subset S = {(1,5),(3,3)} is not realizable. So a(6)=8-1=7.

Crossrefs

Sequence in context: A064410 A304178 A266776 * A363214 A062896 A025065

Adjacent sequences: A371511 A371512 A371513 * A371515 A371516 A371517

Keyword

nonn,more

Author

Dinush Jayasooriya, Mar 26 2024

Status

approved