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