Quartic Graph on:
[Wikipedia]
[Google]
[Amazon]
In the
Several well-known graphs are quartic. They include:
*The
mathematical
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
field of graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, 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 discret ...
where all vertices have degree 4. In other words, a quartic graph is a 4-regular graph
In graph theory, a regular graph is a Graph (discrete mathematics), graph where each Vertex (graph theory), vertex has the same number of neighbors; i.e. every vertex has the same Degree (graph theory), degree or valency. A regular directed graph ...
.
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 i ...
''K''5, 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, de ...
, 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 era to refer to an African American. In many places, it may be considered a slur.
Dictionary definitions
The word ''colored'' wa ...
with three colors.
*The Folkman graph
In the mathematical field of graph theory, the Folkman graph is a 4- regular graph with 20 vertices and 40 edges. It is a regular bipartite graph with symmetries taking every edge to every other edge, but the two sides of its bipartition are not ...
, 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, a quartic graph with 70 vertices that is 4-connected but has no Hamiltonian cycle
In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...
, 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
Plane most often refers to:
* Aero- or airplane, a powered, fixed-wing aircraft
* Plane (geometry), a flat, 2-dimensional surface
* Plane (mathematics), generalizations of a geometrical plane
Plane or planes may also refer to:
Biology
* Plane ...
, and every quartic plane graph is the medial graph of a pair of dual plane graphs or multigraphs. Knot diagram
In 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 be undone, the simplest k ...
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 mor ...
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. The line graph
In the mathematics, mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edge (graph theory), edges of . is constructed in the following way: for each edge i ...
of any cubic graph
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.
A bicubic graph is a cubic bip ...
is quartic; the cuboctahedral graph is an example, as the line graph of a cube graph
In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube.
has vertices, ...
.
Properties
Because the degree of every vertex in a quartic graph is even, everyconnected
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 end ...
.
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 with edges and vertices , a perfect matching in is a subset of , such that every vertex in is adjacent to exact ...
. In this case, a much simpler and faster algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
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
In graph theory, a factor of a graph ''G'' is a spanning subgraph, i.e., a subgraph that has the same vertex set as ''G''. A ''k''-factor of a graph is a spanning ''k''-regular subgraph, and a ''k''-factorization partitions the edges of the gr ...
, 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 theoretical 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 ...
. 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 grap ...
s.
Open problems
It is an open conjecture whether all quartic Hamiltonian graphs have an even number ofHamiltonian 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 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 mor ...
s..
See also
*Cubic graph
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.
A bicubic graph is a cubic bip ...
References
External links
* {{DEFAULTSORT:Quartic Graph Graph families Regular graphs