In the mathematical

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 field of graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, the flower snarks form an infinite family of snark

Snark (graph theory)

In the mathematical field of graph theory, a snark is a connected, bridgeless cubic graph with chromatic index equal to 4. In other words, it is a graph in which every vertex has three neighbors, and the edges cannot be colored by only three colors without two edges of the same color meeting at a...

s introduced by Rufus Isaacs

Rufus Isaacs (game theorist)

Rufus Philip Isaacs was a game theorist especially prominent in the 1950s and 1960s with his work on differential games.-Biography:...

 in 1975.

As snarks, the flower snarks are a connected, bridgeless cubic graph

Cubic graph

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....

s with chromatic index equal to 4. The flower snarks are non-planar

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...

 and non-hamiltonian.

Construction

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

• Build n copies of the star graph on 4 vertices. Denote the central vertex of each star A_i and the outer vertices B_i, C_i and D_i. This results in a disconnected graph on 4n vertices with 3n edges (A_i-B_i, A_i-C_i and A_i-D_i for 1≤i≤n).
• Construct the n-cycle (B₁... B_n). This adds n edges.
• Finally construct the 2n-cycle (C₁... C_nD₁... D_n). This adds 2n edges.

By construction, the Flower snark J_n 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 sometime used for J₅, a flower snark with 20 vertices

Vertex (graph theory)

In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...

 and 30 edges. It is one of 6 snarks on 20 vertices . The flower snark J₅ is hypohamiltonian

Hypohamiltonian graph

In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.-History:...

.

J₃ is a trivial variation of the Petersen graph

Petersen graph

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it...

 formed by applying a Y-Δ transform to the Petersen graph

Petersen graph

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it...

 and thereby replacing one of its vertices by a triangle. This graph is also known as the Tietze's graph

Tietze's graph

In the mathematical field of graph theory, the Tietze's graph is an undirected cubic graph with 12 vertices and 18 edges, formed by applying a Y-Δ transform to the Petersen graph and thereby replacing one of its vertices by a triangle....

. In order to avoid trivial cases, snarks are generally restricted to have girth at least 5. With that restriction, J₃ is not a snark.