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!)
A182096 Number of simple graphs with n unlabeled vertices with the degree of each vertex a prime number. 0
0, 0, 1, 3, 4, 21, 60, 412, 2912, 48360, 974787, 56958187, 2313100395, 415655894822, 24672742242739 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

A simple graph, also called a strict graph, is an unweighted, undirected graph containing no graph loops or multiple edges. Given an undirected graph, a degree sequence is a monotonic nonincreasing sequence of the vertex degrees (valencies) of its graph vertices.

LINKS

Table of n, a(n) for n=1..15.

Darryn Bryant and Tom McCourt, Graphs with five vertices, Figure 1.

Eric W. Weisstein, MathWorld: Simple Graph

EXAMPLE

a(3) = 1 because there is a unique graph with 3 vertices each having prime degree, the triangle, with degree sequence (2,2,2).

a(4) = 3 because there are 3 graphs with 4 vertices each having prime degree: the 4-cycle (2,2,2,2); the complete graph K_4 with degree sequence (3,3,3,3); and two triangle graphs sharing a common edge, with degree sequence (3,3,2,2).

a(5) = 4 because there are 4 graphs with 5 vertices each having prime degree: the 5-cycle with degree sequence (2,2,2,2,2); a square graph sharing an edge with a triangle graph (G_13 in the linked-to illustration) with degree sequence (3,3,2,2,2); G_14 in the linked-to illustration with degree sequence (3,3,2,2,2); G_18 in the linked-to illustration with degree sequence (3,3,3,3,2).

MATHEMATICA

a[n_Integer] :=  Count[And @@ PrimeQ /@ GraphData[#, "Degrees"] & /@ GraphData[n], True] (* Charles R Greathouse IV, Apr 11 2012 *)

show[n_Integer] :=  Map[Graph, GraphData[#, "EdgeRules"] & /@

   Select[GraphData[n], And @@ PrimeQ /@ GraphData[#, "Degrees"] &]] (* Charles R Greathouse IV, Apr 12 2012 *)

CROSSREFS

Cf. A000040, A000088, A004251.

Sequence in context: A156173 A094632 A081698 * A012123 A012255 A012247

Adjacent sequences:  A182093 A182094 A182095 * A182097 A182098 A182099

KEYWORD

nonn,more

AUTHOR

Jonathan Vos Post, Apr 11 2012

EXTENSIONS

a(5)-a(7) from Charles R Greathouse IV, Apr 11 2012

a(8)-a(15) from Andrew Howroyd, Mar 08 2020

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 April 9 20:46 EDT 2020. Contains 333363 sequences. (Running on oeis4.)