In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, the flower snarks form an infinite family of
snarks introduced by
Rufus Isaacs in 1975.
As snarks, the flower snarks are connected, bridgeless
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.
A bicubic graph is a cubic bipa ...
s with
chromatic index
In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...
equal to 4. The flower snarks are
non-planar and
non-hamiltonian. The flower snarks J
5 and J
7 have
book thickness
In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie o ...
3 and
queue number
In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings.
Defin ...
2.
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 4''n'' vertices with 3''n'' edges (A
''i'' – B
''i'', A
''i'' – C
''i'' and A
''i'' – D
''i'' for 1 ≤ ''i'' ≤ ''n'').
* Construct the ''n''-cycle (B
1... B
''n''). This adds ''n'' edges.
* Finally construct the ''2n''-cycle (C
1... C
''n''D
1... D
''n''). This adds ''2n'' edges.
By construction, the Flower snark J
''n'' is a cubic graph with 4''n'' vertices and 6''n'' edges. For it to have the required properties, ''n'' should be odd.
Special cases
The name flower snark is sometimes used for J
5, a flower snark with 20
vertices and 30 edges. It is one of 6 snarks on 20 vertices . The flower snark J
5 is
hypohamiltonian.
J
3 is a trivial variation of the
Petersen graph
In the mathematics, mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertex (graph theory), vertices and 15 edge (graph theory), edges. It is a small graph that serves as a useful example and counterexample for ...
formed by 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, J
3 is not a snark.
Gallery
File:Flower snark 3COL.svg, The chromatic number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
of the flower snark J5 is 3.
File:Flower_snark_4color edge.svg, The chromatic index
In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...
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
In the mathematics, mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertex (graph theory), vertices and 15 edge (graph theory), edges. It is a small graph that serves as a useful example and counterexample for ...
as a graph minor
In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges.
The theory of graph minors began with Wagner's theorem that a graph is planar if and only i ...
of the flower snark J5
References
{{reflist
Parametric families of graphs
Regular graphs