<p>A bipartite graph <i>B</i> is called a brace if it is connected and every matching of size at most two in <i>B</i> is contained in some perfect matching of <i>B</i>. A conformal cross over some cycle <i>C</i> is a pair of disjoint paths <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(P_1\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(P_2\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> which are internally disjoint from <i>C</i>, the endpoints of each path separate the endpoints of the other path on <i>C</i>, and both <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(C\cup P_1\cup P_2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>C</mi> <mo>∪</mo> <msub> <mi>P</mi> <mn>1</mn> </msub> <mo>∪</mo> <msub> <mi>P</mi> <mn>2</mn> </msub> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(B-(V(C)\cup V(P_1)\cup V(P_2))\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>B</mi> <mo>-</mo> <mo stretchy="false">(</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <mi>C</mi> <mo stretchy="false">)</mo> </mrow> <mo>∪</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mn>1</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mo>∪</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> have a perfect matching. We show that if <i>C</i> is a 4-cycle in a brace <i>B</i>, then <i>C</i> has a a conformal cross if and only if <i>B</i> contains <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(K_{3,3}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mrow> <mn>3</mn> <mo>,</mo> <mn>3</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> as a matching minor. This result implies a polynomial time algorithm which solves the 2-linkage problem for alternating paths in bipartite graphs with perfect matchings.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Two Disjoint Alternating Paths in Bipartite Graphs: Conformal Crosses

  • Archontia C. Giannopoulou,
  • Sebastian Wiederrecht

摘要

A bipartite graph B is called a brace if it is connected and every matching of size at most two in B is contained in some perfect matching of B. A conformal cross over some cycle C is a pair of disjoint paths \(P_1\) P 1 , \(P_2\) P 2 which are internally disjoint from C, the endpoints of each path separate the endpoints of the other path on C, and both \(C\cup P_1\cup P_2\) C P 1 P 2 and \(B-(V(C)\cup V(P_1)\cup V(P_2))\) B - ( V ( C ) V ( P 1 ) V ( P 2 ) ) have a perfect matching. We show that if C is a 4-cycle in a brace B, then C has a a conformal cross if and only if B contains \(K_{3,3}\) K 3 , 3 as a matching minor. This result implies a polynomial time algorithm which solves the 2-linkage problem for alternating paths in bipartite graphs with perfect matchings.