## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  374.05047
Autor:  Erdös, Paul; Meir, A.
Title:  On total matching numbers and total covering numbers of complementary graphs. (In English)
Source:  Discrete Math. 19, 229-233 (1977).
Review:  A vertex u of a graph G is said to cover itself, all incident edges, and all adjacent vertices. An edge uv of G covers itself, u and v, and all adjacent edges. A subset S of V(G)\cup E(G) is called a total cover if the elements of S cover G. Two elements of V(G)\cup E(G) are said to be independent if neither covers the other. Define \alpha2(G) = max|S|, where the min is taken over all total covers S of G, and \beta2(G) = max|T| , where the max is taken over all subsets T of V(G)\cup E(G) whose elements are pairwise independent. The following theorems are presented.
Theorem 1: If G is a graph on n vertices, then

2{n/2} \leq \beta2(G)+\beta2(\overline G) \leq {3n/2}.

The upper bound is best possible for all n, the lower bound is best possible for all n\ne 2(mod 4).
Theorem 2: If G is a graph on n vertices, then

{n/2}+1 \leq \alpha2(G)+\alpha2(\overline G) \leq {3n/2}.

The upper bound is best possible for all n, the lower bound is best possible for odd n.
Theorem 3: If G is a connected graph on n \geq 2 vertices, then

\alpha2(G)+\beta2(G) \leq n+{n/2}/2.

This bound is best possible.
Reviewer:  L.Lesniak-Foster
Classif.:  * 05C99 Graph theory
05B40 Packing and covering (combinatorics)

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag