Regular packing of rooted hyperforests with root constraints in hypergraphs

• 成果类型: Article
• 署名作者: Hoppenot, Pierre; Martin, Mathis; Szigeti, Zoltan
• 署名单位: Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02167-z
• 发表日期: 2025
• 页码: 1211-1233

摘要

The seminal papers of Edmonds (Combinatorial algorithms, Academic Press, New York, 1973), Nash-Williams (J Lond Math Soc 36:445-450, 1961) and Tutte (J Lond Math Soc 36:221-230, 1961) have laid the foundations of the theories of packing arborescences and packing trees. The directed version has been extensively investigated, resulting in a great number of generalizations. In contrast, the undirected version has been marginally considered. The aim of this paper is to further develop the theories of packing trees and forests. Our main result on graphs characterizes the existence of a packing of k forests, F1,& mldr;,Fk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_1, \ldots , F_k$$\end{document}, in a graph G such that each vertex of G belongs to exactly h of the forests, the number of connected components of each Fi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_i$$\end{document} is between & ell;(i)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell (i)$$\end{document} and & ell;'(i)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell '(i)$$\end{document} and the total number of connected components in the packing is between alpha\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha $$\end{document} and beta\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}. Finally, we extend this result to hypergraphs and dypergraphs, the latter giving a generalization of a theorem of B & eacute;rczi and Frank (Math Oper Res 43(3):726-753, 2018). As a matter of fact, this research was motivated by the paper of B & eacute;rczi and Frank (Math Oper Res 43(3):726-753, 2018).