Multiple vertex coverings by specified induced subgraphs

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

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.
10 pages, 3 figures

Keywords

Combinatorics, 05C35, 05C70

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/79659

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/9912188
 http://arxiv.org/abs/math/9912188

Collections

arXiv