Optimal packing of induced stars in a graph (Q1367032): Difference between revisions

A subset \(A\) of the edge set of a graph \(G\) is called an induced \(n\)-star packing of \(G\) if every component of the subgraph of \(G\) induced by \(A\) is a star with at most \(n\) edges. The author considers the problem of finding an induced star packing of \(G\) that covers the maximum number of vertices. This problem is a generalization of the classical matching problem. He proves that many fundamental results on matchings can be extended to induced \(n\)-star packings.