From Surf Wiki (app.surf) — the open knowledge base
Diamond graph
Planar graph with 4 nodes and 5 edges
Planar graph with 4 nodes and 5 edges
| Field | Value | |
|---|---|---|
| name | Diamond graph | |
| image | [[Image:Diamond graph.svg | 170px]] |
| vertices | 4 | |
| edges | 5 | |
| automorphisms | 4 (Klein four-group: | |
| diameter | 2 | |
| girth | 3 | |
| radius | 1 | |
| chromatic_number | 3 | |
| chromatic_index | 3 | |
| properties | Hamiltonian | |
| Planar | ||
| Unit distance |
Planar Unit distance
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 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.
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 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.
Algebraic properties
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 with itself.
The characteristic polynomial of the diamond graph is . It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.
References
References
- "Diamond Graph".
- ISGCI: Information System on Graph Classes and their Inclusions "[http://www.graphclasses.org/smallgraphs.html List of Small Graphs]".
- Sin-Min Lee, Y.C. Pan and Ming-Chen Tsai. "On Vertex-graceful (p,p+l)-Graphs". [http://www.cs.sjsu.edu/~lee/publicat_files/On_Vertex_graceful__p__p_1__Graphs.pdf] {{Webarchive. link. (2008-08-07)
- (1988). "The complexity of some edge deletion problems". IEEE Transactions on Circuits and Systems.
This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.
Ask Mako anything about Diamond graph — get instant answers, deeper analysis, and related topics.
Research with MakoFree with your Surf account
Create a free account to save articles, ask Mako questions, and organize your research.
Sign up freeThis content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.
Report