Halin Snark
A Halin snark is a snark constructed from a cubic Halin graph by replacing the vertices of its perimeter cycle with auxiliary graph multipoles. The graph multipoles used by Máčajová and Škoviera (2021) are derived from a cubic graph with perfect matching cover index at least 5 and a bipartite cubic graph.
Every Halin snark has perfect matching cover index at least 5. When the fragments are constructed from cyclically 4-edge-connected cubic graphs of girth at least 5, the resulting Halin snarks are nontrivial snarks, i.e., cyclically 4-edge-connected cubic graphs of girth at least 5.
The family of Halin snarks contains the previously known nontrivial snarks with perfect matching cover index at least 5, including treelike snarks, windmill snarks, and the family constructed by Chen (Máčajová and Škoviera 2021). In particular, for every even integer n>=42, there exists a nontrivial snark on n vertices with perfect matching cover index at least 5. The existence of nontrivial snarks of orders 38 and 40 with perfect matching cover index at least 5 remains open.
The 34- and 46-vertex perfect matching snarks, illustrated above, are Halin snarks that cannot be covered with four perfect matchings and have perfect matching cover index 5. They are implemented in the Wolfram Language as GraphData ["PerfectMatchingSnark34"] and GraphData ["PerfectMatchingSnark46"].
See also
Cubic Graph, Graph Multipole, Halin Graph, Perfect Matching Cover Index, SnarkExplore with Wolfram|Alpha
References
Abreu, M.; Kaiser, T.; Labbate, D.; and Mazzuoccolo, G. "Treelike Snarks." Elec. J. Combin. 23, #P3.54, 2016.Chen, F. "A Note on Fouquet-Vanherpe's Question and Fulkerson Conjecture." Bull. Iranian Math. Soc. 42, 1247-1258, 2016.Esperet, L. and Mazzuoccolo, G. "On Cubic Bridgeless Graphs Whose Edge-Set Cannot Be Covered by Four Perfect Matchings." J. Graph Th. 77, 144-157, 2014.Máčajová, E. and Škoviera, M. "Cubic Graphs That Cannot Be Covered with Four Perfect Matchings." J. Combin. Th. Ser. B 150, 144-176, 2021. https://doi.org/10.1016/j.jctb.202104004.Cite this as:
Weisstein, Eric W. "Halin Snark." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/HalinSnark.html