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

%I

%S 0,0,1,3,4,21,60,412,2912,48360,974787,56958187,2313100395,

%T 415655894822,24672742242739,14476157312171612,1201604193795794073,

%U 4552351087690759156124,597350655972004799844521,142501236416711876143177302627

%N Number of simple graphs with n unlabeled vertices with the degree of each vertex a prime number.

%C 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.

%H Darryn Bryant and Tom McCourt, <a href="http://wiki.smp.uq.edu.au/G-designs/index.php/Graphs_with_five_vertices">Graphs with five vertices</a>, Figure 1.

%H Eric W. Weisstein, <a href="http://mathworld.wolfram.com/SimpleGraph.html">MathWorld: Simple Graph</a>

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

%e 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).

%e 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).

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

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

%t Select[GraphData[n], And @@ PrimeQ /@ GraphData[#, "Degrees"] &]] (* _Charles R Greathouse IV_, Apr 12 2012 *)

%Y Cf. A000040, A000088, A004251.

%K nonn,more

%O 1,4

%A _Jonathan Vos Post_, Apr 11 2012

%E a(5)-a(7) from _Charles R Greathouse IV_, Apr 11 2012

%E a(8)-a(15) from _Andrew Howroyd_, Mar 08 2020

%E a(16)-a(20) from _Andrew Howroyd_, May 03 2020

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 6 13:31 EDT 2020. Contains 334827 sequences. (Running on oeis4.)