Generalizations of Marriage Theorem for Degree Factors

被引:0
|
作者
Radosław Cymer
Mikio Kano
机构
[1] Universität Augsburg,Institut für Informatik
[2] Ibaraki University,undefined
来源
Graphs and Combinatorics | 2016年 / 32卷
关键词
Marriage theorem; Degree factor; Bipartite graph;  -Factor; (g, f)-Factor;
D O I
暂无
中图分类号
学科分类号
摘要
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∪B→{0,1,2,…}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$h: A\cup B \rightarrow \{0,1,2, \ldots \}$$\end{document}, G has a factor F such that degF(x)=h(x)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\deg _F(x)=h(x)$$\end{document} for x∈A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x\in A$$\end{document} and degH(y)≤h(y)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\deg _H(y) \le h(y)$$\end{document} for y∈B\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$y\in B$$\end{document} if and only if h(X)≤∑x∈NG(X)min{h(x),eG(x,X)}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$h(X) \le \sum _{x\in N_G(X)}\min \{h(x), e_G(x,X)\}$$\end{document} for all X⊆A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X\subseteq A$$\end{document}.
引用
收藏
页码:2315 / 2322
页数:7
相关论文
共 50 条