Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 840.05093
Autor: Erdös, Paul; Jacobson, M.S.; Lehel, J.
Title: Graphs realizing the same degree sequences and their respective clique numbers. (In English)
Source: Alavi, Yousef (ed.) et al., Graph theory, combinatorics, and applications, Vol. 1. Proceedings of the sixth quadrennial international conference on the theory and applications of graphs held at Western Michigan University, Kalamazoo, Michigan, May 30-June 3, 1988. New York: John Wiley & Sons Ltd. Wiley-Interscience Publication. 439-449 (1991).
Review: There are several characterizations of graphical sequences, yet only little work on the possible structure of these graphs. We begin considering the question of the possible clique number attained by graphs with the same degree sequence. In particular, it is shown that the maximum difference between the largest and the smallest possible clique number for graphs realizing the same degree sequence of n elements is n- cn2/3 for sufficiently large n. Additional results on sequences having a realization H with \omega(H) \geq k are presented.
Classif.: * 05C99 Graph theory
Keywords: graphical sequences; clique number; degree sequence; realization
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag