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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page