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 ...
, the diamond graph is a
planar,
undirected graph with 4
vertices and 5 edges. It consists of a
complete graph minus one edge.
The diamond graph has radius 1,
diameter
In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid for ...
2,
girth
Girth may refer to:
;Mathematics
* Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space
* Girth (geometry), the perimeter of a parallel projection of a shape
* Girth ...
3,
chromatic number 3 and
chromatic index 3. It is also a 2-
vertex-connected and a 2-
edge-connected,
graceful
Gracefulness, or being graceful, is the physical characteristic of displaying "pretty agility", in the form of elegant movement, poise, or balance. The etymological root of ''grace'' is the Latin word ''gratia'' from ''gratus'', meaning pleasing ...
,
Hamiltonian graph
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 ...
.
Diamond-free graphs and forbidden minor
A graph is diamond-free if it has no diamond as an
induced subgraph. The
triangle-free graphs are diamond-free graphs, since every diamond contains a triangle. The diamond-free graphs are locally clustered: that is, they are the graphs in which every
neighborhood
A neighbourhood (British English, Irish English, Australian English and Canadian English) or neighborhood (American English; see spelling differences) is a geographically localised community within a larger city, town, suburb or rural area, ...
is a
cluster graph
In graph theory, a branch of mathematics, a cluster graph is a graph formed from the disjoint union of complete graphs.
Equivalently, a graph is a cluster graph if and only if it has no three-vertex induced path; for this reason, the cluster gra ...
. Alternatively, a graph is diamond-free if and only if every pair of maximal cliques in the graph shares at most one vertex.
The family of graphs in which each
connected component is a
cactus graph
In graph theory, a cactus (sometimes called a cactus tree) is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or ( ...
is
downwardly closed under
graph minor
In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges.
The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...
operations. This graph family may be characterized by a single
forbidden minor
In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden ...
. This minor is the diamond graph.
[.]
If both the
butterfly graph
In the mathematical field of graph theory, the butterfly graph (also called the bowtie graph and the hourglass graph) is a planar, undirected graph with 5 vertices and 6 edges. It can be constructed by joining 2 copies of the cycle graph with a ...
and the diamond graph are forbidden minors, the family of graphs obtained is the family of
pseudoforests.
Algebraic properties
The full automorphism group of the diamond graph is a group of order 4 isomorphic to the
Klein four-group
In mathematics, the Klein four-group is a Group (mathematics), group with four elements, in which each element is Involution (mathematics), self-inverse (composing it with itself produces the identity)
and in which composing any two of the three ...
, the
direct product
In mathematics, one can often define a direct product of objects already known, giving a new one. This generalizes the Cartesian product of the underlying sets, together with a suitably defined structure on the product set. More abstractly, one ta ...
of the
cyclic group with itself.
The
characteristic polynomial
In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The chara ...
of the diamond graph is . It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.
See also
*
Vámos matroid
References
{{reflist
Individual graphs