Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 244.05114
Autor: Chvatal, V.; Erdös, Paul; Hedrlin, Z.
Title: Ramsey's theorem and self-complementary graphs. (In English)
Source: Discrete Math. 3, 301-304 (1972).
Review: A graph G is called s-good if neither G nor its complement contains a complete graph with s+1 vertices. By Ramsey's theorem, given any s there is the least integer n(s) such that no graph with more than n(s) vertices is s-good. Let n^*(s) be the largest number of vertices of a self-complementary s-good graph. Then n^*(s) \leq n(s). One has n^*(2) = n(2) = 5 and n^*(3) = n(3) = 17; perhaps n^*(s) = n(s) for all s. The authors prove n^*(st) \geq (n^*(s)-1)n(t); in particular, n^*(2t) \geq 4n(t). The last inequality together with an earlier exponential lower bound on n(s), due to Erdös, yields an exponential lower bound on n^*(s). An application to Shannon's notion of a capacity of G is mentioned.
Classif.: * 05C99 Graph theory
05C35 Extremal problems (graph theory)
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag