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 λ₁ ≤ ... ≤ λ_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,K₁) is the independence number of G. We present upper bounds on α(G,H) generalizing the result α(G,K₁) ≤ frac{-λ₁}{r-λ₁}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,K₁) ≤ frac{-λ₁λ_n}{δ²-λ₁λ_n}n. In case H=K₁, our bounds are not comparable with that one of W.H. Haemers. Furthermore, we generalize the result α(G,K₁) ≤ 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