DIMACS TR: 96-31
Packing of induced stars in a graph
Author: Alexander K. Kelmans
ABSTRACT
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