Vertex Covers by Edge Disjoint Cliques |
| |
| Authors: | Tom Bohman Alan Frieze Miklós Ruszinkó Lubos Thoma |
| |
| Affiliation: | (1) Department of Mathematical Sciences, Carnegie Mellon University; Pittsburgh, PA 15213, USA; E-mail: tbohman@andrew.cmu.edu, US;(2) Department of Mathematical Sciences, Carnegie Mellon University; Pittsburgh, PA 15213, USA; E-mail: alan@random.math.cmu.edu, US;(3) Department of Mathematical Sciences, Carnegie Mellon University; Pittsburgh, PA 15213, USA; Permanent Address: Computer and Automation Research Institute of the Hungarian Academy of Sciences; Budapest, P.O.Box 63, H-1518, Hungary; E-mail: ruszinko@lutra.sztaki.hu, HU;(4) Department of Mathematical Sciences, Carnegie Mellon University; Pittsburgh, PA 15213, USA; E-mail: thoma@qwes.math.cmu.edu, US |
| |
| Abstract: | ![]()
Dedicated to the memory of Paul Erdős Let H be a simple graph having no isolated vertices. An (H,k)-vertex-cover of a simple graph G = (V,E) is a collection of subgraphs of G satisfying 1. , for all i = 1, ..., r, 2. , 3. , for all , and 4. each is in at most k of the . We consider the existence of such vertex covers when H is a complete graph, , in the context of extremal and random graphs. Received October 31, 1999 RID="*" ID="*" Supported in part by NSF grant DMS-9627408. RID="†" ID="†" Supported in part by NSF grant CCR-9530974. RID="‡" ID="‡" Supported in part by OTKA Grants T 030059 and T 29074, FKFP 0607/1999 and by the Bolyai Foundation. RID="§" ID="§" Supported in part by NSF grant DMS-9970622. |
| |
| Keywords: | AMS Subject Classification (2000) Classes: 05C80, 05C35 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
