A371514 - OEIS

%I #25 Apr 20 2024 10:35:31

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

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

%C 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.

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

%e 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.

%K nonn,more

%O 1,2

%A _Dinush Jayasooriya_, Mar 26 2024