ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

13. Combinatorics

1991 MS Classification: 05 Spresser, Diane M., James Madison University, USA (Currently at NSF) Graphs with degree sets of maximal cardinality II. Graph G = (V, E) is finite, undirected, and simple. Its degree set is the set of degrees of the vertices of G. For each integer p > 1, there are exactly two graphs G∗ and G ∗ ∗ of order p whose degree sets have maximal cardinality. We derive results that characterize G∗ and G ∗ ∗. We further exhibit an algorithm that, given the two graphs G∗ and G ∗ ∗ of order p > 1, generates the two graphs of order p + 1. Reference: D. Spresser, Another handshaking problem: graphs of order p whose degree sets contain p−1 elements, Int. J. Math. Educ. Sci. Technol. 27 (1996), 247–252.