\(M\)-alternating paths in \(n\)-extendable bipartite graphs (Q1402062): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Derek Holton / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Stanlislav Jendroľ / rank | |||
Normal rank |
Revision as of 17:17, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(M\)-alternating paths in \(n\)-extendable bipartite graphs |
scientific article |
Statements
\(M\)-alternating paths in \(n\)-extendable bipartite graphs (English)
0 references
19 August 2003
0 references
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.
0 references
\(M\)-alternating paths
0 references
\(n\)-extendable
0 references