Multiple vertex coverings by specified induced subgraphs
| dc.creator | Furedi, Zoltan | |
| dc.creator | Mubayi, Dhruv | |
| dc.creator | West, Douglas B. | |
| dc.date | 1999-12-22 | |
| dc.date.accessioned | 2026-07-07T05:32:26Z | |
| dc.date.available | 2026-07-07T05:32:26Z | |
| dc.description | Given graphs H_1,...,H_k, we study the minimum order of a graph G such that for each i, the induced copies of H_i in G cover V(G). We prove a general upper bound of twice the sum of the numbers m_i, where m_i is one less than the order of H_i. When k=2 and one graph is an independent set of size n, we determine the optimum within a constant. When k=2 and the graphs are a star and an independent set, we determine the answer exactly. | |
| dc.description | 10 pages, 3 figures | |
| dc.identifier | https://arxiv.org/abs/math/9912188 | |
| dc.identifier | http://arxiv.org/abs/math/9912188 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/79659 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C35, 05C70 | |
| dc.title | Multiple vertex coverings by specified induced subgraphs | |
| dc.type | text |