In graph theory, the Loupekine snarks are an infinite family of snarks, graphs with three edges per vertex that cannot be partitioned into three perfect matchings. Their construction is credited to Féodor Loupekine in a 1976 technical report published by Rufus Isaacs. Loupekine's 1992 doctoral dissertation includes the construction, and attaches Isaac's technical report as an appendix, but this appendix has been redacted from the online version of the dissertation.
Construction It involves forming an odd number of blocks by removing three-vertex paths from smaller snarks, and arranging the blocks into a cycle. Consecutive pairs of blocks in this cycle are connected by pairs of edges, attached in each block to two degree-two vertices in the block, the two neighbors of one endpoint of the removed path. These connections leave one remaining degree-two vertex in each block, a neighbor of the central vertex of the removed path. These remaining vertices are connected by adding to them a "central graph", attached to each degree-two vertex by a single edge and having degree three at its other vertices. This construction produces a graph that has no 3-color edge coloring, regardless of the central graph. This is because in any 3-edge-coloring of a block and its connecting edges, one pair of edges connecting to an adjacent block in the cycle of blocks must have a single color and the other pair must have two different colors. This alternation between edge pairs with one or two colors cannot be maintained consistently around an odd cycle of blocks. When the central graph is chosen in a way that maintains the connectivity requirements of a snark, the result is a snark.
Examples The simplest Loupekine snarks are obtained by constructing three blocks from three copies of the Petersen graph, connecting them by pairs of edges into a cycle of three blocks, and using a central graph consisting of a three-leaf star. There are two graphs of this type, depending on how the pairs of edges connecting consecutive blocks are chosen. They both have 22 vertices and 33 edges, and have an order-6 dihedral group of symmetries. Both graphs are 1-planar.
References
External links No. 263, Isaacs: "Loupekine's Snarks: A Bifamily of Non-Tait- Colorable Graphs," 1976, catalog record of a printed copy of Isaac's original 1976 publication in the special collections of the Johns Hopkins University libraries
