0

A matching in a graph is a set of edges that are pair-wise non-adjacent. IOW, each node involved in the matching appears in only one edge.

Now I am wondering is there a ``generalized'' concept of matching, such that it still refers to an edge-set, and each vertex involved can appear in at most $k$ edges in this edge-set, where $k \ge 2$ is a pre-specified positive integer.

If such concept does exist, what are some interesting and representative problems studied for that?

user16416
  • 1
  • 3
  • 2
    See this: http://cstheory.stackexchange.com/questions/17724/what-is-complexity-of-this-max-edge-subgraph-problem/17727#17727 – Austin Buchanan Jun 20 '13 at 20:53
  • 2
    They are typically called b-matchings and are very well-studied. Most books on combinatorial optimization will give an introduction to this topic after treating matchings. You can check Schrijver's book for instance. – Chandra Chekuri Jun 22 '13 at 14:58

1 Answers1

2

A short answer is http://en.wikipedia.org/wiki/Graph_factorization. A more comprehensive reference might be the classic "Matching Theory" by Lovasz and Plummer, which is the best on this topic.

Yixin Cao
  • 2,560
  • 1
  • 16
  • 29