##
**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 \alpha_{2}(G) = **max**|S|, where the min is taken over all total covers S of G, and \beta_{2}(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 \beta_{2}(G)+\beta_{2}(\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 \alpha_{2}(G)+\alpha_{2}(\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

\alpha_{2}(G)+\beta_{2}(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