Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 882.05077
Autor: Erdös, Paul; Simonovits, M.; Sós, Vera T.; Rao, S.B.
Title: On totally supercompact graphs. (In English)
Source: Sankhya, Ser. A 54, Spec. Vol., 155-167 (1992).
Review: A graph is said to be totally supercompact, if for any two vertices x and y there is a vertex z\ne x,y joined to one of them but not to the other. In this paper, (i) three problems of G. L. Chia and O. K. Lim on totally supercompact selfcomplementary graphs are solved; (ii) we determine the maximum number of edges f(n,p) in a totally supercompact graph of order n without Kp, solving a problem of Hoffman. We also solve a generalization of this problem for so-called k-asymmetrical graphs.
Classif.: * 05C35 Extremal problems (graph theory)
Keywords: totally supercompact graph; problem of Hoffman
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag