Double-star snark

In the mathematical field of graph theory, the double-star snark is a snark with 30 vertices and 45 edges.[1]

Double-star snark
The Double-star snark
Vertices30
Edges45
Radius4
Diameter4
Girth6
Automorphisms80
Chromatic number3
Chromatic index4
Book thickness3
Queue number2
PropertiesSnark
Hypohamiltonian
Table of graphs and parameters

In 1975, Rufus Isaacs introduced two infinite families of snarks—the flower snark and the BDS snark, a family that includes the two Blanuša snarks, the Descartes snark and the Szekeres snark (BDS stands for Blanuša Descartes Szekeres).[2] Isaacs also discovered one 30-vertex snark that does not belong to the BDS family and that is not a flower snark — the double-star snark.

As a snark, the double-star graph is a connected, bridgeless cubic graph with chromatic index equal to 4. The double-star snark is non-planar and non-hamiltonian but is hypohamiltonian.[3] It has book thickness 3 and queue number 2.[4]

References

  1. Weisstein, Eric W. "Double Star Snark". MathWorld.
  2. Isaacs, R. (1975), "Infinite families of non-trivial trivalent graphs which are not Tait-colorable", American Mathematical Monthly, Mathematical Association of America, 82 (3): 221–239, doi:10.2307/2319844, JSTOR 2319844
  3. Weisstein, Eric W. "Hypohamiltonian Graph". MathWorld.
  4. Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.