

A233387


Number of labeled star graphs with added edges.


0



32, 185, 1308, 10822, 102176, 1081908, 12681640, 162880256, 2273437392, 34249286656, 553698389888, 9558929197560, 175471796530816, 3412297318315472, 70064350595106336, 1514554957975079008, 34377185731361631680
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

4,1


COMMENTS

Here, a star graph is a tree on n nodes (n>=4) with one specially designated (center) vertex, v of degree n1. 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 n1 through each noncenter 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.
If we don't add any edges we have a star graph and there are n labelings.
If we add exactly one edge then we produce a cycle of length 3 and we no longer have a tree.
If we add the maximum number of edges we get a wheel graph A171005.


LINKS



FORMULA

Ignoring the first 4 terms the e.g.f. is: x*exp(A(x))+ x*(log(1/(1x))/2 + x^2/4 + x/2) where A(x) = x/(1x)/2 + x/2.


EXAMPLE

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.


MATHEMATICA

nn=20; a=x/(1x)/2+x/2; Drop[Range[0, nn]! CoefficientList[Series[x Exp[a]+x (Log[1/(1x)]/2+x^2/4+x/2), {x, 0, nn}], x], 4]


CROSSREFS

Cf. A013989 (with appropriate offset) enumerates such graphs where the maximum degree of noncenter vertices is restricted to 2.


KEYWORD

nonn


AUTHOR



STATUS

approved



