login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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 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/(1-x))/2 + x^2/4 + x/2) where A(x)=x/(1-x)/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/(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]

CROSSREFS

Cf. A013989 (with appropriate offset) enumerates such graphs where the maximum degree of non-center 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 1 04:57 EDT 2020. Contains 334758 sequences. (Running on oeis4.)