Navigation

Inhalt Hotkeys
Fakultät für Mathematik
Fakultät für Mathematik
Jochen Harant, Sebastian Richter, Horst Sachs: Packing of induced subgraphs

Jochen Harant, Sebastian Richter, Horst Sachs: Packing of induced subgraphs


Author(s):
Jochen Harant
Sebastian Richter
Horst Sachs
Title:
Jochen Harant, Sebastian Richter, Horst Sachs: Packing of induced subgraphs
Electronic source:
application/pdf
Preprint series:
Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 14, 2013
Mathematics Subject Classification:
05C69 []
05C70 []
05C50 []
Abstract:
Let G be a simple, undirected, and connected graph on n ≥ 2 vertices with eigenvalues λ1 ≤ ... ≤ λn. Motivated by research to upper bounds on independence, the following concept of graph packing is considered. Two vertex disjoint induced subgraphs H and H' of G are independent in G if G does not contain an edge between H and H'. Let α(G,H) be the maximum number of vertex disjoint copies of H contained in G as induced and pairwise independent subgraphs. Note that α(G,K1) is the independence number of G. We present upper bounds on α(G,H) generalizing the result α(G,K1) ≤ frac{1}{r-λ1}n of A.J. Hoffman for an r-regular graph G. If G is an arbitrary graph with minimum degree δ, then W.H. Haemers extended Hoffman's inequality to α(G,K1) ≤ frac{1λn}{δ21λn}n. In case H=K1, our bounds are not comparable with that one of W.H. Haemers. Furthermore, we generalize the result α(G,K1) ≤ min{|{i|λi ≤ 0}|,|{i|λi ≥ 0}|} of D.M. Cvetković. The possibility to derive lower bounds on α(G,H) is discussed. The results are used to derive upper bounds also for the ordinary packing number, where the condition of independence of the copies of H is dropped.
Keywords:
independence number, packing of graphs
Language:
English
Publication time:
08/2013

Presseartikel