Odd subgraphs and matchings (Q1613457)

This paper studies a generalisation of matchings called \((1,f)\)-odd subgraphs. The function \(f\) maps vertices of a graph \(G\) to odd natural numbers. A subgraph \(H\) of \(G\) is \((1,f)\)-odd if the degree of each vertex \(v\) in \(H\) is odd and does not exceed \(f(v)\). Matchings correspond to the case when \(f\) is constant with value \(1\). The aim of the paper is to investigate which properties of matchings generalise to \((1,f)\)-odd subgraphs. Maximal and maximum \((1,f)\)-odd subgraphs are defined by comparing subgraphs according to which vertices they cover, but ignoring edges. Under this definition, it is shown that all maximal \((1,f)\)-odd subgraphs are maximum. A formula for the order of a maximum \((1,f)\)-odd subgraph is given. This formula is a direct generalisation of the equivalent formula for matchings. While most of the paper deals with properties of matchings which generalise to \((1,f)\)-odd subgraphs, an example is given to show that not all properties of matchings do generalise in the most obvious way.