Flower snark
Template:Short description <templatestyles src="Infobox graph/styles.css"/>Script error: No such module "Infobox".
<templatestyles src="Infobox graph/styles.css"/>Script error: No such module "Infobox".
In the mathematical field of graph theory, the flower snarks form an infinite family of snarks introduced by Rufus Isaacs in 1975.[1]
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 :
- 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.[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.
Gallery
-
The chromatic number of the flower snark J5 is 3.
-
The chromatic index of the flower snark J5 is 4.
-
The original representation of the flower snark J5.
-
The Petersen graph as a graph minor of the flower snark J5
References
<templatestyles src="Reflist/styles.css" />
Script error: No such module "Check for unknown parameters".