Premium
ON THE PRODUCT OF THE POINT AND LINE COVERING NUMBERS OF A GRAPH
Author(s) -
Chung F. R. K.,
Erdös P.,
Graham R. L.
Publication year - 1979
Publication title -
annals of the new york academy of sciences
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.712
H-Index - 248
eISSN - 1749-6632
pISSN - 0077-8923
DOI - 10.1111/j.1749-6632.1979.tb32840.x
Subject(s) - annals , citation , library science , combinatorics , mathematics , computer science , history , classics
where G ranges over all graphs with n points . He further noted that equality holds in 61 forthe star K,,,_, and in (ii) for the complete graph K,, . In this note we settle these conjectures . In particular, we show that (i) is true, and ,ii), while not completely true, is nearly true . The smallest countterexampl . to (ii) is the graph 2K3 consisting of two disjoint triangles . Note that a0(2K3),xt(2K3) = 16, ao(K6)o:,(K6) = 15 . imvover (1!) k valid it n ±3 odd o .' : G is reclinred to be connected! . "Vc nlst : consider' the corresponding questions for hypergraplis .