Watkins snark

Last updated
Watkins snark
Watkins snark.svg
The Watkins snark
Named after J. J. Watkins
Vertices 50
Edges 75
Radius 7
Diameter 7
Girth 5
Automorphisms 5
Chromatic number 3
Chromatic index 4
Book thickness 3
Queue number 2
Properties Snark
Table of graphs and parameters

In the mathematical field of graph theory, the Watkins snark is a snark with 50 vertices and 75 edges. [1] [2] It was discovered by John J. Watkins in 1989. [3]

Mathematics Field of study concerning quantity, patterns and change

Mathematics includes the study of such topics as quantity, structure, space, and change.

Graph theory Area of discrete mathematics

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

Snark (graph theory) connected, bridgeless cubic graph with chromatic index equal to 4

In the mathematical field of graph theory, a snark is a simple, connected, bridgeless cubic graph with chromatic index equal to 4. In other words, it is a graph in which every vertex has three neighbors, the connectivity is redundant so that removing no one edge would split the graph, and the edges cannot be colored by only three colors without two edges of the same color meeting at a point. In order to avoid trivial cases, snarks are often restricted to have girth at least 5.

Contents

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

Bridge (graph theory) An edge in a node-link graph whose removal would disconnect the graph

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases its number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

Cubic graph node-link graphs in which every vertex is incident to exactly three edges

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

Another well known snark on 50 vertices is the Szekeres snark, the fifth known snark, discovered by George Szekeres in 1973. [5]

Szekeres snark

In the mathematical field of graph theory, the Szekeres snark is a snark with 50 vertices and 75 edges. It was the fifth known snark, discovered by George Szekeres in 1973.

George Szekeres Hungarian-Australian mathematician

George Szekeres AM FAA was a Hungarian–Australian mathematician.

Edges

[[1,2], [1,4], [1,15], [2,3], [2,8], [3,6], [3,37], [4,6], [4,7], [5,10], [5,11], [5,22], [6,9], [7,8], [7,12], [8,9], [9,14], [10,13], [10,17], [11,16], [11,18], [12,14], [12,33], [13,15], [13,16], [14,20], [15,21], [16,19], [17,18], [17,19], [18,30], [19,21], [20,24], [20,26], [21,50], [22,23], [22,27], [23,24], [23,25], [24,29], [25,26], [25,28], [26,31], [27,28], [27,48], [28,29], [29,31], [30,32], [30,36], [31,36], [32,34], [32,35], [33,34], [33,40], [34,41], [35,38], [35,40], [36,38], [37,39], [37,42], [38,41], [39,44], [39,46], [40,46], [41,46], [42,43], [42,45], [43,44], [43,49], [44,47], [45,47], [45,48], [47,50], [48,49], [49,50]]

Related Research Articles

Double-star snark graph with 30 vertices and 45 edges

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

Ljubljana graph

In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges.

Statistics of Swedish football Division 3 in season 2011.

Statistics of Swedish football Division 3 in season 2009.

Statistics of Swedish football Division 3 in season 2008.

Statistics of Swedish football Division 3 in season 2007.

Statistics of Swedish football Division 3 in season 2006.

Statistics of Swedish football Division 3 in season 2003.

Statistics of Swedish football Division 3 in season 2002.

Statistics of Swedish football Division 3 in season 2001.

Statistics of Swedish football Division 3 in season 2000.

Statistics of Swedish football Division 3 in season 1999.

Statistics of Swedish football Division 3 in season 1998.

Statistics of Swedish football Division 3 in season 1994.

Statistics of Swedish football Division 3 in season 1993.

1990 Soviet Lower Second League was the second season of the Soviet Second League B since its reestablishing in 1990. As in the last season it was divided into 10 zones (groups).

1989 Soviet Second League was a Soviet competition in the Soviet Second League.

1989 Soviet Second League was a Soviet competition in the Soviet Second League.

References

  1. Weisstein, Eric W. "Watkins Snark". MathWorld .
  2. Watkins, J. J. and Wilson, R. J. "A Survey of Snarks." In Graph Theory, Combinatorics, and Applications (Ed. Y. Alavi, G. Chartrand, O. R. Oellermann, and A. J. Schwenk). New York: Wiley, pp. 1129-1144, 1991
  3. Watkins, J. J. "Snarks." Ann. New York Acad. Sci. 576, 606-622, 1989.
  4. Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
  5. Szekeres, G. (1973). "Polyhedral decompositions of cubic graphs". Bull. Austral. Math. Soc. 8 (03): 367387. doi:10.1017/S0004972700042660.