Flower snark
{{Short description|Infinite family of graphs}}
{{infobox graph
| name = Flower snark
| image = 220px
| image_caption = The flower snarks J3, J5 and J7.
| namesake =
| notation = Jn with n odd
| vertices = 4n
| edges = 6n
| girth = 3 for n=3
5 for n=5
6 for n≥7
| chromatic_number = 3
| chromatic_index = 4
| properties = Snark for n≥5
|book thickness=3 for n=5
3 for n=7|queue number=2 for n=5
2 for n=7}}
{{infobox graph
| name = Flower snark J5
| image = 220px
| image_caption = The flower snark J5.
| namesake =
| vertices = 20
| edges = 30
| girth = 5
| chromatic_number = 3
| chromatic_index = 4
| properties = Snark
Hypohamiltonian
}}
In the mathematical field of graph theory, the flower snarks form an infinite family of snarks introduced by Rufus Isaacs in 1975.{{cite journal |last=Isaacs |first=R. |title=Infinite Families of Nontrivial Trivalent Graphs Which Are Not Tait Colorable |journal=Amer. Math. Monthly |volume=82 |pages=221–239 |year=1975 |doi=10.1080/00029890.1975.11993805 |jstor=2319844}}
As snarks, the flower snarks are connected, bridgeless cubic graphs with chromatic index equal to 4. The flower snarks are non-planar and non-Hamiltonian. The flower snarks J5 and J7 have book thickness 3 and queue number 2.Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
Construction
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.
Special cases
The name flower snark is sometimes used for J5, a flower snark with 20 vertices and 30 edges.{{MathWorld|title=Flower Snark|urlname=FlowerSnark}} It is one of 6 snarks on 20 vertices {{OEIS|id=A130315}}. The flower snark J5 is hypohamiltonian.{{MathWorld|title=Hypohamiltonian Graph|urlname=HypohamiltonianGraph}}
J3 is a trivial variation of the Petersen graph formed by replacing one of its vertices by a triangle. This graph is also known as the Tietze's graph.{{citation|first1=L.|last1=Clark|first2=R.|last2=Entringer|title=Smallest maximally nonhamiltonian graphs|journal=Periodica Mathematica Hungarica|volume=14|issue=1|year=1983|pages=57–68|doi=10.1007/BF02023582}}. In order to avoid trivial cases, snarks are generally restricted to have girth at least 5. With that restriction, J3 is not a snark.
Gallery
File:Flower snark 3COL.svg|The chromatic number of the flower snark J5 is 3.
File:Flower_snark_4color edge.svg|The chromatic index of the flower snark J5 is 4.
File:Flower_snark_original.svg|The original representation of the flower snark J5.
File:Flower-Petersen-minor.svg|The Petersen graph as a graph minor of the flower snark J5