Disjoint matchings of graphs
Autor: | Kenneth Lebensold |
---|---|
Jazyk: | angličtina |
Předmět: | |
Zdroj: | Journal of Combinatorial Theory, Series B. (3):207-210 |
ISSN: | 0095-8956 |
DOI: | 10.1016/0095-8956(77)90066-1 |
Popis: | In this paper, we prove a generalization of the familiar marriage theorem. One way of stating the marriage theorem is: Let G be a bipartite graph, with parts S 1 and S 2 . If A ⊂ S 1 and F ( A ) ⊂ S 2 is the set of neighbors of points in A , then a matching of G exists if and only if Σ x ∈ S 2 min(1, | F −1 ( x ) ∩ A |) ≥ | A | for each A ⊂ S 1 . Our theorem is that k disjoint matchings of G exist if and only Σ x ∈ S 2 min ( k , | F −1 ( x ) ∩ A |) ≥ k | A | for each A ⊂ S 1 . |
Databáze: | OpenAIRE |
Externí odkaz: |