DIMACS TR: 96-31

Packing of induced stars in a graph

Author: Alexander K. Kelmans


We consider simple undirected graphs. An edge subset $A$ of $G$ is called an {\em induced $n$--star packing} of $G$ if every component of the subgraph $G[A]$ induced by $A$ is a star with at most $n$ edges and is an induced subgraph of $G$. We consider the problem of finding an induced $n$--star packing of $G$ that covers the maximum number of vertices. This problem is a natural generalization of the classical matching problem. We show that many classical results on matchings (such as the Tutte 1-Factor Theorem, the Berge Duality Theorem, the Gallai--Edmonds Structure Theorem, the Matching Matroid Theorem) can be extended to induced $n$--star packings in a graph.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-31.ps.gz
DIMACS Home Page