Back to Home Page
.
Snark Graphs
.
Random Graphs(not available yet)
.

Snark Graphs

To understand what a snark graph is we need to define some things first:
  • In graph theory, a bridge is a edge if and only if is not contained in any cycle. A graph with no bridges is a bridgeless graph.
  • The edge chromatic number of a graph G is fewest number of colors necessary to color each edge of G such that no two edges incident on the same vertex have the same color.

A snark is a connected bridgeless cubic graph with edge chromatic number of four. By Vizing's theorem, the edge chromatic number of every cubic graph is either three or four, so a snark corresponds to the special case of four. Snarks are therefore class 2 graphs.We can see an example on Fig. 1.

Snark graphs are interesting because we know so little about them. Writting in The Electronic Journal of Combinatorics, Miroslav Chladny states that:

"In the study of various important and difficult problems in graph theory (such as the Cycle double cover conjecture and the 5-Flow Conjecture), one 4encounters an interesting but somewhat mysterious variety of graphs called snarks. In spite of their simple denition...and over a century long investiga- tion, their properties and structure are largely unknown.[1]"
flower J5 with the dominating set
Fig. 1 - Flower J5 snark with its dominating set in red


Snark input file

Snarks

Dominating set in snarks

There's not a lot of studies of dominating set on snark graphs. So I present instead, the results of my program for some of the snark graphs in the input file.
  1. (1,1)Blanusa snark - 18 vertices:
    Minumum dominating set of size: 5
  2. Flower snark J5 - 20 vertices:
    Minimum dominating set of size 6
  3. Double star graph - 30 vertices:
    Minimum dominating set of size: 8
  4. Flower snark J7 - 28 vertices:
    Minumum dominating set of size: 7
  5. Goldberg snark 7 - 56 vertices:
    Minimum dominating set of size: 16
  6. Loupekine's first snark - 22 vertices:
    Minimum dominating set of size: 6
We can observe that the size of the dominating set tends to be close to 1/3 of the number of vertex. Which makes sense since all vertices have a degree of 3 and we want to keep the number of times a vertex is dominated to a minimum.

References

  1. Chladny, Miroslav; Martin Skoviera. Factorisation of snarks. The Electronic Journal of Combinatorics, 17:R32, 2010.