Flower snark

Flower snark
The flower snarks J3, J5 and J7.
Vertices4n
Edges6n
Girth3 for n=3
5 for n=5
6 for n≥7
Chromatic number3
Chromatic index4
Book thickness3 for n=5
3 for n=7
Queue number2 for n=5
2 for n=7
PropertiesSnark for n≥5
NotationJn with n odd
Table of graphs and parameters
Flower snark J5
The flower snark J5.
Vertices20
Edges30
Girth5
Chromatic number3
Chromatic index4
PropertiesSnark
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]

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, though they are 1-planar.[2] The flower snarks J5 and J7 have book thickness 3 and queue number 2.[3]

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

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.[6] 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 (3): 221–239. doi:10.1080/00029890.1975.11993805. JSTOR 2319844.
  2. ^ Pupyrev, Sergey (2025), "OOPS: Optimized One-Planarity Solver via SAT", in Dujmović, Vida; Montecchiani, Fabrizio (eds.), Proc. 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025), Leibniz International Proceedings in Informatics (LIPIcs), vol. 357, pp. 14:1–14:19, doi:10.4230/LIPIcs.GD.2025.14, ISBN 978-3-95977-403-1.
  3. ^ Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
  4. ^ Weisstein, Eric W. "Flower Snark". MathWorld.
  5. ^ Weisstein, Eric W. "Hypohamiltonian Graph". MathWorld.
  6. ^ Clark, L.; Entringer, R. (1983), "Smallest maximally nonhamiltonian graphs", Periodica Mathematica Hungarica, 14 (1): 57–68, doi:10.1007/BF02023582.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.