Odd subgraphs and matchings
type: Item
instance of: scholarly article
title: Odd subgraphs and matchings
zbMATH Open document ID: 0996.05099
DOI: 10.1016/S0012-365X(01)00424-1
author: Gyula Y. Katona
author: Mikio Kano
published in: Discrete Mathematics
publication date: 2002-08-29T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1792389
zbMATH Keywords: matching
zbMATH Keywords: odd subgraph
zbMATH Keywords: graph factor
reviewed by: Ian M. Wanless
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00424-1
OpenAlex ID: W2168309835
Recommended article: Q3572929
Recommended article: Matchings in graphs of odd regularity and girth
Recommended article: Q5588434
Recommended article: Subconstituents of orthogonal graphs of odd characteristic
Recommended article: On matchings in graphs
Recommended article: Sub-Ramsey numbers for matchings
Recommended article: Q3640664
Recommended article: Subgraphs of maximum matching graphs
Recommended article: Q3767382
Recommended article: Subgraphs of random match-graphs
description: scientific article; zbMATH DE number 1792389