In 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 ...

, the diamond graph is a planar,

undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

with 4 vertices and 5 edges. It consists of a

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

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 centre of the circle and whose endpoints lie on the circle. It can also be defined as the longest Chord (geometry), chord of the circle. Both definitions a ...

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

chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

3 and chromatic index 3. It is also a 2- vertex-connected and a 2- edge-connected, graceful, Hamiltonian graph.

Diamond-free graphs and forbidden minor

A graph is diamond-free if it has no diamond as an

induced subgraph In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) ...

. 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 (Commonwealth English) or neighborhood (American English) is a geographically localized community within a larger town, city, suburb or rural area, sometimes consisting of a single street and the buildings lining it. Neigh ...

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 g ...

. 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 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, 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. This minor is the diamond graph.. If both the

butterfly graph In the mathematics, mathematical field of graph theory, the butterfly graph (also called the bowtie graph and the hourglass graph) is a planar graph, planar, undirected graph with 5 Vertex (graph theory), vertices and 6 edges. It can be construct ...

and the diamond graph are forbidden minors, the family of graphs obtained is the family of

pseudoforest In graph theory, a pseudoforest is an undirected graphThe kind of undirected graph considered here is often called a multigraph or pseudograph, to distinguish it from a simple graph. in which every Connected component (graph theory), connected com ...

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 an abelian 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 non-identi ...

, the

direct product In mathematics, a direct product of objects already known can often be defined by giving a new one. That induces a structure on the Cartesian product of the underlying sets from that of the contributing objects. The categorical product is an abs ...

of the

cyclic group In abstract algebra, a cyclic group or monogenous group is a Group (mathematics), group, denoted C_n (also frequently \Z_n or Z_n, not to be confused with the commutative ring of P-adic number, -adic numbers), that is Generating set of a group, ge ...

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

of the diamond graph is . It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.

References

{{reflist Individual graphs

Diamond-free graphs and forbidden minor

Algebraic properties

See also

References