In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory 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'' (also called ''nodes'' or ''points'') which are conne ...

, a quartic graph is a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

where all vertices have

degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathematics ...

4. In other words, a quartic graph is a 4-

regular graph In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree o ...

Examples

Several well-known graphs are quartic. They include: *The

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...

''K''₅, a quartic graph with 5 vertices, the smallest possible quartic graph. *The

Chvátal graph In the mathematical field of graph theory, the Chvátal graph is an undirected graph with 12 vertices and 24 edges, discovered by Václav Chvátal in 1970. It is the smallest graph that is triangle-free, 4-regular, and 4-chromatic. Coloring, d ...

, another quartic graph with 12 vertices, the smallest quartic graph that both has no triangles and cannot be

colored ''Colored'' (or ''coloured'') is a racial descriptor historically used in the United States during the Jim Crow, Jim Crow Era to refer to an African Americans, African American. In many places, it may be considered a Pejorative, slur, though it ...

with three colors. *The

Folkman graph Folkman may refer to: People * Jens Christian Folkman Schaanning, a Norwegian politician * Jon Folkman, an American mathematician * Judah Folkman, an American medical scientist * Roy Folkman, an Israeli politician Math * Folkman graph, a type of ...

, a quartic graph with 20 vertices, the smallest

semi-symmetric graph In the mathematical field of graph theory, a semi-symmetric graph is an undirected graph that is edge-transitive and regular, but not vertex-transitive. In other words, a graph is semi-symmetric if each vertex has the same number of incident edg ...

. *The

Meredith graph In the mathematical field of graph theory, the Meredith graph is a 4- regular undirected graph with 70 vertices and 140 edges discovered by Guy H. J. Meredith in 1973. The Meredith graph is 4- vertex-connected and 4- edge-connected, has chromati ...

, a quartic graph with 70 vertices that is 4-connected but has no

Hamiltonian cycle In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

, disproving a conjecture of

Crispin Nash-Williams Crispin St John Alvah Nash-Williams FRSE (19 December 1932 – 20 January 2001) was a British mathematician. His research interest was in the field of discrete mathematics, especially graph theory. Biography Nash-Williams was born on 19 Decemb ...

. Every

medial graph In the mathematical discipline of graph theory, the medial graph of plane graph ''G'' is another graph ''M(G)'' that represents the adjacencies between edges in the faces of ''G''. Medial graphs were introduced in 1922 by Ernst Steinitz to study ...

is a quartic

plane graph 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 ...

, and every quartic plane graph is the medial graph of a pair of dual plane graphs or multigraphs.

Knot diagram In the mathematical field of topology, knot theory is the study of mathematical knots. While inspired by knots which appear in daily life, such as those in shoelaces and rope, a mathematical knot differs in that the ends are joined so it cannot ...

s and link diagrams are also quartic plane

multigraph In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by more ...

s, in which the vertices represent the crossings of the diagram and are marked with additional information concerning which of the two branches of the knot crosses the other branch at that point.

Properties

Because the

of every vertex in a quartic graph is even, every

connected Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...

quartic graph has an

Euler tour In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends ...

. And as with regular bipartite graphs more generally, every bipartite quartic graph has a

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...

. In this case, a much simpler and faster

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

for finding such a matching is possible than for irregular graphs: by selecting every other edge of an Euler tour, one may find a 2-factor, which in this case must be a collection of cycles, each of even length, with each vertex of the graph appearing in exactly one cycle. By selecting every other edge again in these cycles, one obtains a perfect matching in

linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

. The same method can also be used to color the edges of the graph with four colors in linear time. Quartic graphs have an even number of

Hamiltonian decomposition In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed graph ...

Open problems

It is an open conjecture whether all quartic Hamiltonian graphs have an even number of

Hamiltonian circuit In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

s, or have more than one Hamiltonian circuit. The answer is known to be false for quartic

s..

References

External links

* {{DEFAULTSORT:Quartic Graph Graph families Regular graphs

Examples

Properties

Open problems

See also

References

External links