
Abstract by
Lubos Thoma
Carnegie Mellon University
- Vertex covers by edge disjoint cliques.
Let t > 1 be an integer. A (t,2)-vertex-cover of a graph G = (V,E) is a collection of edge disjoint subgraphs of G, each isomorphic to the
complete graph Kt, such that the collection covers every vertex in V either
once or twice. Consider the graph process G0, G1, G2,... in which we start with the empty graph and add edges (chosen uniformly
at random) one at a time. We consider two hitting times. Let T1 be the least m for which every vertex in Gm is contained in a copy of Kt,
and let T2 be the least m for which Gm has a (t,2)-vertex-cover. We show that with high probability T1 = T2. This result is related to a well known conjecture of Erdos and Spencer concerning the existence of K3-factors in the
random graph. (Joint work with T. Bohman, A. Frieze, and M. Ruszinko.)
- Tuesday, September 5, 2000, 3:00 p.m. - 345 Altgeld Hall
GRAPH THEORY AND COMBINATORICS
Go Back