<p>The complementary prism <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_22_Article_IEq1.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="31" /> </InlineMediaObject> <EquationSource Format="TEX">\(G{\overline{G}}\)</EquationSource> </InlineEquation> is the graph obtained by taking a copy of a simple graph <i>G</i> and a copy of its complement <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_22_Article_IEq2.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\({\overline{G}}\)</EquationSource> </InlineEquation>, and then linking with an edge each pair of corresponding vertices. In 2019, it was shown that every non-regular complementary prism <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_22_Article_IEq1.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="31" /> </InlineMediaObject> <EquationSource Format="TEX">\(G{\overline{G}}\)</EquationSource> </InlineEquation> is <i>Class 1</i> (i.e.&#xa0;<InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_22_Article_IEq4.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="54" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Delta (G{\overline{G}})\)</EquationSource> </InlineEquation>-edge-colourable), and it was conjectured that the Petersen graph is the only <i>Class 2</i> (i.e.&#xa0;not <i>Class 1</i>) complementary prism. We provide further evidence for this conjecture by showing that asymptotically almost every <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_22_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(d\)</EquationSource> </InlineEquation>-regular complementary prism has at least <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_22_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="141" /> </InlineMediaObject> <EquationSource Format="TEX">\(4\lfloor h / 3\rfloor + (h \bmod 3)\)</EquationSource> </InlineEquation> pairwise-disjoint perfect matchings, being <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_22_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="100" /> </InlineMediaObject> <EquationSource Format="TEX">\(h =(d - 3) / 2\)</EquationSource> </InlineEquation>.</p>

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

Asymptotically Almost Every Regular Complementary Prism has Many Pairwise-Disjoint Perfect Matchings

  • Leandro M. Zatesko

摘要

The complementary prism \(G{\overline{G}}\) is the graph obtained by taking a copy of a simple graph G and a copy of its complement \({\overline{G}}\) , and then linking with an edge each pair of corresponding vertices. In 2019, it was shown that every non-regular complementary prism \(G{\overline{G}}\) is Class 1 (i.e.  \(\Delta (G{\overline{G}})\) -edge-colourable), and it was conjectured that the Petersen graph is the only Class 2 (i.e. not Class 1) complementary prism. We provide further evidence for this conjecture by showing that asymptotically almost every \(d\) -regular complementary prism has at least \(4\lfloor h / 3\rfloor + (h \bmod 3)\) pairwise-disjoint perfect matchings, being \(h =(d - 3) / 2\) .