Zentralblatt MATH

Publications of (and about) Paul Erdös

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,


\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

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page