Concept

Diamond graph

In the mathematical field of graph theory, the diamond graph is a planar, undirected graph with 4 vertices and 5 edges. It consists of a complete graph K_4 minus one edge. The diamond graph has radius 1, diameter 2, girth 3, chromatic number 3 and chromatic index 3. It is also a 2-vertex-connected and a 2-edge-connected, graceful, Hamiltonian graph. 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 is a cluster graph. 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 operations. This graph family may be characterized by a single forbidden minor. This minor is the diamond graph. If both the butterfly graph and the diamond graph are forbidden minors, the family of graphs obtained is the family of pseudoforests. The full automorphism group of the diamond graph is a group of order 4 isomorphic to the Klein four-group, the direct product of the cyclic group \mathbb{Z} / 2\mathbb{Z} with itself. The characteristic polynomial of the diamond graph is x(x+1)(x^2-x-4). It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.