cp's OEIS Frontend

A233387 Number of labeled star graphs with added edges.

%I A233387 #38 Aug 01 2021 01:56:12
%S A233387 32,185,1308,10822,102176,1081908,12681640,162880256,2273437392,
%T A233387 34249286656,553698389888,9558929197560,175471796530816,
%U A233387 3412297318315472,70064350595106336,1514554957975079008,34377185731361631680
%N A233387 Number of labeled star graphs with added edges.
%C A233387 Here, a star graph is a tree on n nodes (n>=4) with one specially designated (center) vertex, v of degree n-1.  We are allowed to add edges so that the degree of any node (excepting v) is at most 3 and so that every cycle includes the vertex v with the possible exception of a single cycle of length n-1 through each non-center vertex. We note that anytime edges are added the original "center" node remains specially designated.  a(n) is the number of such connected simple labeled graphs with a specially designated node.
%C A233387 If we don't add any edges we have a star graph and there are n labelings.
%C A233387 If we add exactly one edge then we produce a cycle of length 3 and we no longer have a tree.
%C A233387 If we add the maximum number of edges we get a wheel graph A171005.
%F A233387 Ignoring the first 4 terms the e.g.f. is: x*exp(A(x))+ x*(log(1/(1-x))/2 + x^2/4 + x/2) where A(x) = x/(1-x)/2 + x/2.
%e A233387 a(4) = 32. There are 4 labelings for the star graph on 4 nodes. There are 12 labelings after we add one edge. There are 12 labelings after we add two edges. There are 4 labelings after we add 3 edges. 4+12+12+4=32.
%t A233387 nn=20; a=x/(1-x)/2+x/2; Drop[Range[0,nn]! CoefficientList[Series[x Exp[a]+x (Log[1/(1-x)]/2+x^2/4+x/2), {x,0,nn}], x], 4]
%Y A233387 Cf. A013989 (with appropriate offset) enumerates such graphs where the maximum degree of non-center vertices is restricted to 2.
%K A233387 nonn
%O A233387 4,1
%A A233387 _Geoffrey Critzer_, Feb 02 2014