|
|
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, 14476157312171612, 1201604193795794073, 4552351087690759156124, 597350655972004799844521, 142501236416711876143177302627
(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
|
|
|
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"] & /@
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|