Zbl.No: 483.05053
Autor: Chung, F.R.K.; Erdös, Paul; Graham, Ronald L.
Title: On the product of the point and line covering numbers of a graph. (In English)
Source: Combinatorial mathematics, 2nd int. Conf., New York 1978, Ann. New York Acad. Sci. 319, 597-602 (1979).
Review: [For the entire collection see Zbl 468.00005.] For a graph G = (V,E) let the point covering number \alpha_{0}(G) and the line covering number \alpha_{1}(G) be defined as follows: \alpha_{0}(G) = max{|X|: X\subseteq V and every e in E contains some x in X} \alpha_{1}(G) = max{|Y|: Y\subseteq E and every v in V is contains in some y in Y}. The authors answer conjectures of F.Harary and J.A.Kabell (in the same proceedings, Zbl 483.05037) by proving that:

\alpha_{0}(G)\alpha_{1}(G) \geq n-1,

and

\alpha_{0}(G)\alpha_{1}(G) \leq

{\frac{n^{2}-1}{2} for n odd,

\frac{n^{2}-4}{2} for n even.

(cases of equality are characterized).
Reviewer: J.C.Bermond
Classif.: * 05C70 Factorization, etc. 05C35 Extremal problems (graph theory)
Keywords: point covering number; line covering number
Citations: Zbl.468.00005