The flower snarks J3, J5 and J7.
|Girth||3 for n=3
5 for n=5
6 for n≥7
|Properties||Snark for n≥5|
|Notation||Jn with n odd|
|Flower snark J5|
The flower snark J5.
The flower snark Jn can be constructed with the following process :
- Build n copies of the star graph on 4 vertices. Denote the central vertex of each star Ai and the outer vertices Bi, Ci and Di. This results in a disconnected graph on 4n vertices with 3n edges (Ai-Bi, Ai-Ci and Ai-Di for 1≤i≤n).
- Construct the n-cycle (B1... Bn). This adds n edges.
- Finally construct the 2n-cycle (C1... CnD1... Dn). This adds 2n edges.
By construction, the Flower snark Jn is a cubic graph with 4n vertices and 6n edges. For it to have the required properties, n should be odd.
The name flower snark is sometimes used for J5, a flower snark with 20 vertices and 30 edges. It is one of 6 snarks on 20 vertices (sequence A130315 in OEIS). The flower snark J5 is hypohamiltonian.
J3 is a trivial variation of the Petersen graph formed by applying a Y-Δ transform to the Petersen graph and thereby replacing one of its vertices by a triangle. This graph is also known as the Tietze's graph. In order to avoid trivial cases, snarks are generally restricted to have girth at least 5. With that restriction, J3 is not a snark.
- Isaacs, R. "Infinite Families of Nontrivial Trivalent Graphs Which Are Not Tait Colorable." Amer. Math. Monthly 82, 221–239, 1975.
- Weisstein, Eric W., "Flower Snark", MathWorld.
- Weisstein, Eric W., "Hypohamiltonian Graph", MathWorld.
- Clark, L.; Entringer, R. (1983), "Smallest maximally nonhamiltonian graphs", Periodica Mathematica Hungarica 14 (1): 57–68, doi:10.1007/BF02023582.
|This combinatorics-related article is a stub. You can help Wikipedia by expanding it.|