The perfect matching cover index of a graph G, denoted by <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2893_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="36" /> </InlineMediaObject> <EquationSource Format="TEX">$\tau (G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>τ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, is the minimum number of perfect matchings needed to cover all the edges of G. Berge conjectured that <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2893_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="67" /> </InlineMediaObject> <EquationSource Format="TEX">$\tau (G)\le 5$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>τ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≤</mo> <mn>5</mn> </mrow> </math></EquationSource> </InlineEquation> for any bridgeless cubic graph G. Esperet and Mazzuoccolo [J. Graph Theory 77(2013) 144–157] proved that deciding whether a bridgeless cubic graph G satisfies <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2893_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="67" /> </InlineMediaObject> <EquationSource Format="TEX">$\tau (G)\le 4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>τ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≤</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation> is NP-complete. Lukot’ka et al. [Electronic J. Combin. 22(1) 2015] constructed a family of high oddness snarks, called LMMS snark. In this paper, a super family of LMMS snarks is constructed, called LMMS superposition, and we prove that there exist some LMMS superpositions such that each of them has perfect matching cover index 4. As a direct corollary, each of LMMS snark has perfect matching cover index 4.

An infinite family of snarks with perfect matching cover index 4

期刊论文
发表日期：

2025年1月24日

查看全文

Wenjuan Zhou,
Rong-Xia Hao,
Zhen He,
Jaeun Lee

摘要

The perfect matching cover index of a graph G, denoted by $\tau (G)$ $τ (G)$ , is the minimum number of perfect matchings needed to cover all the edges of G. Berge conjectured that $\tau (G)\le 5$ $τ (G) \leq 5$ for any bridgeless cubic graph G. Esperet and Mazzuoccolo [J. Graph Theory 77(2013) 144–157] proved that deciding whether a bridgeless cubic graph G satisfies $\tau (G)\le 4$ $τ (G) \leq 4$ is NP-complete. Lukot’ka et al. [Electronic J. Combin. 22(1) 2015] constructed a family of high oddness snarks, called LMMS snark. In this paper, a super family of LMMS snarks is constructed, called LMMS superposition, and we prove that there exist some LMMS superpositions such that each of them has perfect matching cover index 4. As a direct corollary, each of LMMS snark has perfect matching cover index 4.