The twisted graph <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$T_{n}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>T</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> is a drawing of the complete graph with n vertices <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$v_{1},v_{2},\ldots ,v_{n}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>v</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>v</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>v</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> in which two edges <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$v_{i}v_{j}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>v</mi> <mi>i</mi> </msub> <msub> <mi>v</mi> <mi>j</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> (<InlineEquation ID="IEq4"> <EquationSource Format="TEX">$i<j$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mo><</mo> <mi>j</mi> </mrow> </math></EquationSource> </InlineEquation>) and <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$v_{s}v_{t}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>v</mi> <mi>s</mi> </msub> <msub> <mi>v</mi> <mi>t</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> (<InlineEquation ID="IEq6"> <EquationSource Format="TEX">$s<t$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mo><</mo> <mi>t</mi> </mrow> </math></EquationSource> </InlineEquation>) cross if and only if <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$i<s<t<j$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mo><</mo> <mi>s</mi> <mo><</mo> <mi>t</mi> <mo><</mo> <mi>j</mi> </mrow> </math></EquationSource> </InlineEquation> or <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$s<i<j<t.$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mo><</mo> <mi>i</mi> <mo><</mo> <mi>j</mi> <mo><</mo> <mi>t</mi> <mo>.</mo> </mrow> </math></EquationSource> </InlineEquation> We show that for any maximal plane subgraphs S and R of <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$T_{n},$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>T</mi> <mi>n</mi> </msub> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> each containing at least one perfect matching, there is a sequence <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$S=F_0, F_1, \ldots , F_t=R$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <mo>=</mo> <msub> <mi>F</mi> <mn>0</mn> </msub> <mo>,</mo> <msub> <mi>F</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>F</mi> <mi>t</mi> </msub> <mo>=</mo> <mi>R</mi> </mrow> </math></EquationSource> </InlineEquation> of maximal plane subgraphs of <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$T_n,$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>T</mi> <mi>n</mi> </msub> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> also containing perfect matchings, such that for <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$i=0,1, \ldots , t-1,$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mo>=</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>t</mi> <mo>-</mo> <mn>1</mn> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$F_{i+1}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>F</mi> <mrow> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> can be obtained from <InlineEquation ID="IEq14"> <EquationSource Format="TEX">$F_{i}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>F</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation> by a single edge exchange i.e. <InlineEquation ID="IEq15"> <EquationSource Format="TEX">$F_{i+1} = ((F_{i} - e) + f),$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>F</mi> <mrow> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mrow> <mo stretchy="false">(</mo> <mrow> <mo stretchy="false">(</mo> <msub> <mi>F</mi> <mi>i</mi> </msub> <mo>-</mo> <mi>e</mi> <mo stretchy="false">)</mo> </mrow> <mo>+</mo> <mi>f</mi> <mo stretchy="false">)</mo> </mrow> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> where e is an edge of <InlineEquation ID="IEq16"> <EquationSource Format="TEX">$F_{i}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>F</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation> not in <InlineEquation ID="IEq17"> <EquationSource Format="TEX">$F_{i+1}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>F</mi> <mrow> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> and f is an edge of <InlineEquation ID="IEq18"> <EquationSource Format="TEX">$F_{i+1}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>F</mi> <mrow> <mi>i</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> not in <InlineEquation ID="IEq19"> <EquationSource Format="TEX">$F_{i}.$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>F</mi> <mi>i</mi> </msub> <mo>.</mo> </mrow> </math></EquationSource> </InlineEquation>

A note on maximal plane subgraphs of the complete twisted graph containing perfect matchings

期刊论文
发表日期：

2026年6月25日

查看全文

Elsa Omaña-Pulido,
Eduardo Rivera-Campo

摘要

The twisted graph $T_{n}$ $T_{n}$ is a drawing of the complete graph with n vertices $v_{1},v_{2},\ldots ,v_{n}$ $v_{1}, v_{2}, \dots, v_{n}$ in which two edges $v_{i}v_{j}$ $v_{i} v_{j}$ ( $i<j$ $i < j$ ) and $v_{s}v_{t}$ $v_{s} v_{t}$ ( $s<t$ $s < t$ ) cross if and only if $i<s<t<j$ $i < s < t < j$ or $s<i<j<t.$ $s < i < j < t .$ We show that for any maximal plane subgraphs S and R of $T_{n},$ $T_{n},$ each containing at least one perfect matching, there is a sequence $S=F_0, F_1, \ldots , F_t=R$ $S = F_{0}, F_{1}, \dots, F_{t} = R$ of maximal plane subgraphs of $T_n,$ $T_{n},$ also containing perfect matchings, such that for $i=0,1, \ldots , t-1,$ $i = 0, 1, \dots, t - 1,$ $F_{i+1}$ $F_{i + 1}$ can be obtained from $F_{i}$ $F_{i}$ by a single edge exchange i.e. $F_{i+1} = ((F_{i} - e) + f),$ $F_{i + 1} = ((F_{i} - e) + f),$ where e is an edge of $F_{i}$ $F_{i}$ not in $F_{i+1}$ $F_{i + 1}$ and f is an edge of $F_{i+1}$ $F_{i + 1}$ not in $F_{i}.$ $F_{i} .$