Optimal packing of induced stars in a graph
type: Item
instance of: scholarly article
title: Optimal packing of induced stars in a graph
zbMATH Open document ID: 0887.05041
DOI: 10.1016/S0012-365X(96)00121-5
author: Alexander Kelmans
published in: Discrete Mathematics
publication date: 1998-04-28T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1062444
zbMATH Keywords: packing
zbMATH Keywords: induced star
reviewed by: Brian Alspach
MaRDI profile type: Publication
cites work: On factors with given components
cites work: Q5422499
cites work: An extension of matching theory
cites work: Packings by cliques and by finite families of graphs
cites work: On the Complexity of General Graph Factor Problems
cites work: Packings by Complete Bipartite Graphs
cites work: Q4141828
cites work: Q4303878
cites work: An extension of Tutte's 1-factor theorem
cites work: On matroids induced by packing subgraphs
cites work: Q3972010
cites work: Efficient subgraphs packing
cites work: Matching theory
cites work: Q4111952
description: scientific article; zbMATH DE number 1062444