A004251 -id:A004251 - cp's OEIS frontend

A338513 a(n) is the number of Chvátal-satisfying spurious graphical n-sequences.

2, 3, 14, 31, 117, 278, 956, 2578, 8106

Offset: 5

Stefano Spezia, Nov 09 2020

Douglas Bauer, Linda Lesniak, Aori Nevo, and Edward Schmeichel, On the necessity of Chvátal’s Hamiltonian degree condition, AKCE International Journal of Graphs and Combinatorics. See p. 2.
Vacláv Chvátal, On Hamilton’s ideals, J. Combin. Theory Ser. B 12(2): 163-168 (1972).

Cf. A000569, A004251, A338512 (non-spurious version).

Conjectures from Bauer et al.: (Start)
Lim_{n->infinity} a(n)/a(n-1) = 3.
Lim_{n->infinity} a(n)/A338512(n) = 0. (End)

A382021 Number of distinct degree sequences among all simple graphs with n vertices whose degrees are consecutive integers.

Original entry on oeis.org

1, 1, 2, 4, 9, 21, 50, 118, 272, 614, 1368, 3014

Offset: 0

John P. McSorley, Mar 12 2025

A sequence of integers is consecutive if its distinct entries are consecutive integers, and a graphic sequence is a sequence of integers that can be the degree sequence of some graph. Thus a(n) is the number of consecutive graphic sequences of length n.

			For n = 5 there are 34 non-isomorphic graphs G on 5 vertices, and 24 of these have a consecutive degree sequence. However consecutive degree sequences 11222, 12223, and 22233 each correspond to 2 non-isomorphic graphs. Thus there are 21 distinct consecutive graphic sequences of length 5, and so a(5)=21.

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford University Press (1999).

Cf. A381586, A000088, A004251, A005176.

a(11) from Sean A. Irvine, Mar 18 2025

A029892 Number of even graphical partitions of order 2n - number of odd graphical partitions of order 2n.

Original entry on oeis.org

1, 3, 8, 27, 88, 313, 1095, 4007, 14511

Offset: 1

TORSTEN.SILLKE(AT)LHSYSTEMS.COM

The graphical partitions considered here are for graphs with 2n vertices and with half-loops allowed. Half-loops are loops which count as 1 towards the degree of the vertex. See A029889 for additional information. - Andrew Howroyd, Jan 11 2024

R. A. Brualdi, H. J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1992.

Index entries for sequences related to graphical partitions

Cf. A000569, A004250, A004251, A029889, A029890, A029891.

Calculated using Cor. 6.3.3, Th. 6.3.6, Cor. 6.2.5 of Brualdi-Ryser.

a(n) = A029891(2*n) - A029890(2*n). - Andrew Howroyd, Jan 10 2024

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

Original entry on oeis.org

0, 0, 1, 3, 4, 21, 60, 412, 2912, 48360, 974787, 56958187, 2313100395, 415655894822, 24672742242739, 14476157312171612, 1201604193795794073, 4552351087690759156124, 597350655972004799844521, 142501236416711876143177302627

Offset: 1

Jonathan Vos Post, Apr 11 2012

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.

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

Darryn Bryant and Tom McCourt, Graphs with five vertices, Figure 1.
Eric W. Weisstein, MathWorld: Simple Graph

Cf. A000040, A000088, A004251.

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 *)

a(5)-a(7) from Charles R Greathouse IV, Apr 11 2012
a(8)-a(15) from Andrew Howroyd, Mar 08 2020
a(16)-a(20) from Andrew Howroyd, May 03 2020

cp's OEIS Frontend

A338513 a(n) is the number of Chvátal-satisfying spurious graphical n-sequences.

Views

Author

Keywords

Links

Crossrefs

Formula

A382021 Number of distinct degree sequences among all simple graphs with n vertices whose degrees are consecutive integers.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Extensions

A029892 Number of even graphical partitions of order 2n - number of odd graphical partitions of order 2n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions