\(M\)-alternating paths in \(n\)-extendable bipartite graphs
type: Item
instance of: scholarly article
title: \(M\)-alternating paths in \(n\)-extendable bipartite graphs
zbMATH Open document ID: 1021.05058
DOI: 10.1016/S0012-365X(02)00827-0
author: R. E. L. Aldred
author: Dingjun Lou
author: Akira Saito
author: Derek Holton
published in: Discrete Mathematics
publication date: 2003-08-19T00:00:00Z
review text: Let \(n\) be a positive integer and \(G\) be a graph with \(v\) vertices, \(v\geq 2n+2\). \(G\) is said to be \(n\)-extendable if \(G\) has \(n\) independent edges and any \(n\) independent edges of \(G\) are contained in a perfect matching of \(G\). Let \(G\) be a bipartite graph with bipartition \((X,Y)\) which has a perfect matching. It is proved that \(G\) is \(n\)-extendable if and only if for any perfect matching \(M\) of \(G\) and for each pair of vertices \(x\) in \(X\) and \(y\) in \(Y\) there are \(n\) internally disjoint \(M\)-alternating paths connecting \(x\) and \(y\). Furthermore, these \(n\) paths start and end with edges in \(E(G)\backslash M\). This theorem is then generalized. Note that for a perfect matching \(M\) of \(G\) an \(M\)-alternating path \(P\) of \(G\) is a path in \(G\) where edges in \(M\) and edges in \(E(G)\backslash M\) appear on \(P\) alternately.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1967258
zbMATH Keywords: \(M\)-alternating paths
zbMATH Keywords: \(n\)-extendable
reviewed by: Stanislav Jendroľ
MaRDI profile type: Publication
cites work: Q5422499
cites work: Q3360201
cites work: Q4304323
cites work: On the structure of minimally \(n\)-extendable bipartite graphs
cites work: Lower bound of cyclic edge connectivity for \(n\)-extendability of regular graphs
cites work: Matching theory
cites work: On n-extendable graphs
cites work: Q3800093
cites work: Extending matchings in graphs: A survey
cites work: Q4393233
description: scientific article; zbMATH DE number 1967258