Abstract | ||
---|---|---|
Let H be a simple graph having no isolated vertices. An (H; k)-vertex-cover of a simplegraph G = (V; E) is a collection H1 ; : : : ; Hr of subgraphs of G satisfying1. H i= H; for all i = 1; : : : ; r;2. [ri=1 V (H i ) = V ,3. E(H i ) \ E(H j ) = ;; for all i 6= j; and4. each v 2 V is in at most k of the H i .We consider the existence of such vertex covers when H is a complete graph, K t ; t 3, inthe context of extremal and random graphs.1 IntroductionLet H be a simple... |
Year | DOI | Venue |
---|---|---|
2001 | 10.1007/s004930100017 | Combinatorica |
Keywords | Field | DocType |
vertex cover,random graph,satisfiability,complete graph | Discrete mathematics,Combinatorics,Disjoint sets,Vertex (geometry),Loop (graph theory),Vertex (graph theory),Edge cover,Neighbourhood (graph theory),Feedback vertex set,Intersection number (graph theory),Mathematics | Journal |
Volume | Issue | ISSN |
21 | 2 | 0209-9683 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tom Bohman | 1 | 250 | 33.01 |
Alan M. Frieze | 2 | 4837 | 787.00 |
M. Ruszinkó | 3 | 230 | 35.16 |
Lubos Thoma | 4 | 42 | 5.34 |