\(M\)-alternating paths in \(n\)-extendable bipartite graphs (Q1402062): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5422499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3360201 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4304323 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the structure of minimally \(n\)-extendable bipartite graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Lower bound of cyclic edge connectivity for \(n\)-extendability of regular graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Matching theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On n-extendable graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3800093 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Extending matchings in graphs: A survey / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4393233 / rank | |||
Normal rank |
Latest revision as of 09:59, 6 June 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