Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the 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