Loupekine snark
| Loupekine snark (first) | |
|---|---|
 The first Loupekine snark | |
| Vertices | 22 |
| Edges | 33 |
| Radius | 3 |
| Diameter | 4 |
| Girth | 5 |
| Chromatic number | 3 |
| Chromatic index | 4 |
| Properties | not planar |
| Table of graphs and parameters | |
| Loupekine snark (second) | |
|---|---|
 The second Loupekine snark | |
| Vertices | 22 |
| Edges | 33 |
| Radius | 3 |
| Diameter | 4 |
| Girth | 5 |
| Chromatic number | 3 |
| Chromatic index | 4 |
| Properties | not planar |
| Table of graphs and parameters | |
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.[1] 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.[2]
Construction
[edit]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.[1]
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.[3] When the central graph is chosen in a way that maintains the connectivity requirements of a snark, the result is a snark.
Examples
[edit]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.[3]
References
[edit]- ^ a b Karam, Kaio; Campos, C. N. (2014), "Fulkerson's conjecture and Loupekine snarks", Discrete Mathematics, 326: 20–28, doi:10.1016/j.disc.2014.02.016, MR 3188983
- ^ Loupekine, Feodor (October 1992), Approaches to the four colour theorem (Ph.D. thesis), The Open University, doi:10.21954/OU.RO.0000E032
- ^ a b Berman, Leah Wrenn; Oliveros, Déborah; Williams, Gordon I. (2024), "Rotationally symmetric snarks from voltage graphs", Discrete Mathematics, 347 (4): Paper No. 113874, 15, doi:10.1016/j.disc.2024.113874, MR 4694305; previously announced as "Cyclic pseudo-Loupekine snarks", arXiv:1707.05294
External links
[edit]- 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