

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 any time 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

Table of n, a(n) for n=4..20.


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.
Sequence in context: A316543 A306058 A317236 * A200840 A208925 A212863
Adjacent sequences: A233384 A233385 A233386 * A233388 A233389 A233390


KEYWORD

nonn


AUTHOR

Geoffrey Critzer, Feb 02 2014


STATUS

approved



