We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Generalizations of Marriage Theorem for Degree Factors.
- Authors
Cymer, Radosław; Kano, Mikio
- Abstract
Let G be a bipartite graph with bipartition ( A, B). We give new criteria for a bipartite graph to have an f -factor, a ( g, f)-factor and other factors together with some applications of these criteria. These criteria can be considered as direct generalizations of Hall's marriage theorem. Among some results, we prove that for a function $$h: A\cup B \rightarrow \{0,1,2, \ldots \}$$ , G has a factor F such that $$\deg _F(x)=h(x)$$ for $$x\in A$$ and $$\deg _H(y) \le h(y)$$ for $$y\in B$$ if and only if $$h(X) \le \sum _{x\in N_G(X)}\min \{h(x), e_G(x,X)\}$$ for all $$X\subseteq A$$ .
- Subjects
MARRIAGE theorem; GENERALIZATION; BIPARTITE graphs; SET theory; COMBINATORICS
- Publication
Graphs & Combinatorics, 2016, Vol 32, Issue 6, p2315
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-016-1699-6