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 \alpha0(G) and the line covering number \alpha1(G) be defined as follows: \alpha0(G) = max{|X|: X\subseteq V and every e in E contains some x in X} \alpha1(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:
\alpha0(G)\alpha1(G) \geq n-1,
and
\alpha0(G)\alpha1(G) \leq
{\frac{n2-1}{2} for n odd,
\frac{n2-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
