In the graph theory, the “Flowers” snarks form an endless family of snarks introduced by Isaacs Rufus in 1975 [1] .
| Snarks “Flower” J 3 , J 5 and J 7 . | |
|---|---|
 | |
| Top | 4 n |
| Riber | 6 n |
| Girth | 3 for n = 3 5 for n = 5 6 for n≥7 |
| Chromatic number | 3 |
| Chromatic Index | four |
| The properties | snark for n≥5 |
| Snark "Flower" J 5 | |
|---|---|
 | |
| Top | 20 |
| Riber | thirty |
| Girth | five |
| Chromatic number | 3 |
| Chromatic Index | four |
| The properties | snark hypogamiltons |
Like all snarks, flowers are connected cubic graphs without bridges with a chromatic index of 4. They are not planar and not Hamiltonian .
Build
Flower J n can be built by the following process:
- We form n copies of a star with 4 vertices. Denote the center of each star by A i , and the outer vertices by B i , C i and D i . The result is a disconnected graph with 4 n vertices and 3 n edges (A i -B i , A i -C i and A i -D i for 1≤ i ≤ n ).
- We form a cycle of length n (B 1 ... B n ). This will add n edges.
- We form a cycle of length 2n (C 1 ... C n D 1 ... D n ). This will add another 2n edges.
By construction, the flower J n is a cubic graph with 4 n vertices and 6 n edges. To get the necessary properties, n must be odd.
Special Cases
The name "flower" is sometimes used for J 5 , a snap with 20 vertices and 30 edges [2] . This is one of 6 20-vertex snarks (sequence A130315 in OEIS ). Flower J 5 is hypogamiltonian [3] .
J 3 is a trivial version of the Petersen graph , obtained by applying the star-triangle transformation to the Petersen graph , and then replacing one of the vertices with a triangle. This graph is also known as the Titze graph [4] . To avoid trivial cases, usually graphs with a girth of less than 5 are not considered snarks. If you follow these restrictions, J 3 snark is not.
Gallery
chromatic number of flower J 5 is 3
the chromatic index of the flower J 5 is 4.
Initial presentation of the flower J 5 .
Notes
- ↑ Isaacs R. Infinite Families of Nontrivial Trivalent Graphs Which Are Not Tait Colorable // Amer. Math: Monthly. - 1975 .-- T. 82 . - S. 221–239 .
- ↑ Weisstein, Eric W. Flower Snark ( Wolfram ) at Wolfram MathWorld .
- ↑ Weisstein, Eric W. Hypohamiltonian Graph on Wolfram MathWorld .
- ↑ L. Clark, R. Entringer. Smallest maximally nonhamiltonian graphs // Periodica Mathematica Hungarica. - 1983 .-- T. 14 , no. 1 . - S. 57-68 . - DOI : 10.1007 / BF02023582 .