A generalization of Hall's theorem for $k$-uniform $k$-partite hypergraphs
عنوان مقاله: A generalization of Hall's theorem for $k$-uniform $k$-partite hypergraphs
شناسه ملی مقاله: JR_COMB-8-3_004
منتشر شده در در سال 1398
شناسه ملی مقاله: JR_COMB-8-3_004
منتشر شده در در سال 1398
مشخصات نویسندگان مقاله:
Reza Jafarpour-Golzari - Department of Mathematics, Institute for Advanced Studies in Basic Science (IASBS), Zanjan, Iran
خلاصه مقاله:
Reza Jafarpour-Golzari - Department of Mathematics, Institute for Advanced Studies in Basic Science (IASBS), Zanjan, Iran
In this paper we prove a generalized version of Hall's theorem in graphs, for hypergraphs. More precisely, let $\mathcal{H}$ be a $k$-uniform $k$-partite hypergraph with some ordering on parts as $V_{۱}, V_{۲},\ldots,V_{k}$ such that the subhypergraph generated on $\bigcup_{i=۱}^{k-۱}V_{i}$ has a unique perfect matching. In this case, we give a necessary and sufficient condition for having a matching of size $t=|V_{۱}|$ in $\mathcal{H}$. Some relevant results and counterexamples are given as well.
کلمات کلیدی: $k$-uniform $k$-partite hypergraph, matching, perfect matching, vertex cover, Hall۰۳۹;s theorem
صفحه اختصاصی مقاله و دریافت فایل کامل: https://civilica.com/doc/1194864/