Another Proof of the Generalized Tutte--Berge Formula for f-Bounded Subgraphs

MaRDI QIDQ6442471zbMATH OpenFDO

Authors Zishen Qu, Douglas B. West

Publication date 3 July 2023

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Given a nonnegative integer weight $f(v)$ for each vertex $v$ in a multigraph $G$, an {it $f$-bounded subgraph} of $G$ is a multigraph $H$ contained in $G$ such that $d_H(v)lef(v)$ for all $vinV(G)$. Using Tutte's $f$-Factor Theorem, we give a new proof of the min-max relation for the maximum size of an $f$-bounded subgraph of $G$. When $f(v)=1$ for all $v$, the formula reduces to the classical Tutte--Berge Formula for the maximum size of a matching.

This page was built for publication: Another Proof of the Generalized Tutte--Berge Formula for $f$-Bounded Subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6442471)