Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 479.05054
Autor: Erdös, Paul; Schuster, S.
Title: Existence of complementary graphs with specified independence numbers. (In English)
Source: The theory and applications of graphs, 4th int. Conf., Kalamazoo/ Mich. 1980, 343-349 (1981).
Review: [For the entire collection see Zbl 459.00006.]
For a graph G, \beta(G) will denote the (vertex)-independence number and \beta1(G) the edge-independence number. In a paper of G. Chartrand and S. Schuster [Trans. New York Acad. Sci. II. Ser. 36, 247-251 (1974; Zbl 275.05110)] sharp upper and lower bounds were given for \beta(G)+\beta(\bar G), \beta(G)·\beta(G), \beta1(G)+\beta1(\bar G) and \beta1(G)·\beta1(\bar G). For example, it was shown for a graph G on p vertices that [P/2] \leq \beta1(G)+\beta1(\bar G) and 0 \leq \beta1(G)·\beta1(\bar G) \leq [P/2]2. In this paper the existence of complementary graphs that realize the independence numbers and edge-independence numbers in the intervals allowed by the Chartrand-Schuster inequalities are considered.
Reviewer: R.Faudree
Classif.: * 05C70 Factorization, etc.
05C35 Extremal problems (graph theory)
05C55 Generalized Ramsey theory
Keywords: independence numbers; edge-independence numbers
Citations: Zbl.459.00006; Zbl.275.05110
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag