Premium
Multiple vertex coverings by specified induced subgraphs
Author(s) -
Füredi Zoltán,
Mubayi Dhruv,
West Douglas B.
Publication year - 2000
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/1097-0118(200006)34:2<180::aid-jgt7>3.0.co;2-l
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , discrete mathematics
Given graphs H 1 ,…, H k , let f ( H 1 ,…, H k ) be 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 constructively that f ( H 1 , H 2 ) ≤ 2( n ( H 1 ) + n ( H 2 ) − 2); equality holds when H 1 = H 2 = K n . We prove that f ( H 1 , K n ) = n + 2√δ( H 1 ) n + O (1) as n → ∞. We also determine f ( K 1, m −1 , K n ) exactly. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 180–190, 2000