Flower snark

Last updated
Flower snark
Flower snarks.svg
The flower snarks J3, J5 and J7.
Vertices 4n
Edges 6n
Girth 3 for n=3
5 for n=5
6 for n≥7
Chromatic number 3
Chromatic index 4
Book thickness 3 for n=5
3 for n=7
Queue number 2 for n=5
2 for n=7
Properties Snark for n≥5
NotationJn with n odd
Table of graphs and parameters
Flower snark J5
Flower snarkv.svg
The flower snark J5.
Vertices 20
Edges 30
Girth 5
Chromatic number 3
Chromatic index 4
Properties Snark
Hypohamiltonian
Table of graphs and parameters

In the mathematical field of graph theory, the flower snarks form an infinite family of snarks introduced by Rufus Isaacs in 1975. [1]

Contents

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. [2]

Construction

The flower snark Jn can be constructed with the following process :

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. [3] It is one of 6 snarks on 20 vertices (sequence A130315 in the OEIS ). The flower snark J5 is hypohamiltonian. [4]

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. [5] In order to avoid trivial cases, snarks are generally restricted to have girth at least 5. With that restriction, J3 is not a snark.

References

  1. Isaacs, R. (1975). "Infinite Families of Nontrivial Trivalent Graphs Which Are Not Tait Colorable". Amer. Math. Monthly. 82: 221–239. doi:10.1080/00029890.1975.11993805. JSTOR   2319844.
  2. Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
  3. Weisstein, Eric W. "Flower Snark". MathWorld .
  4. Weisstein, Eric W. "Hypohamiltonian Graph". MathWorld .
  5. Clark, L.; Entringer, R. (1983), "Smallest maximally nonhamiltonian graphs", Periodica Mathematica Hungarica, 14 (1): 57–68, doi:10.1007/BF02023582 .