Graphs in graph theory
Wikimedia gallery | |||||
Upload media | |||||
Instance of |
| ||||
---|---|---|---|---|---|
| |||||
Individual graphs edit
Highly symmetric graphs edit
Strongly regular graphs edit
The strongly regular graph on v vertices and rank k is usually denoted srg(v,k,λ,μ).
-
Paley graph of order 13
Symmetric graphs edit
A symmetric graph is one in which there is a symmetry (graph automorphism) taking any ordered pair of adjacent vertices to any other ordered pair; the Foster census lists all small symmetric 3-regular graphs. Every strongly regular graph is symmetric, but not vice versa.
-
The Rado graph
Semi-symmetric graphs edit
Graph families edit
Complete graphs edit
The complete graph on vertices is often called the -clique and usually denoted , from German komplett.[2]
Complete bipartite graphs edit
The complete bipartite graph is usually denoted . The graph equals the 4-cycle (the square) introduced below.
-
-
, the utility graph
-
-
Cycles edit
The cycle graph on vertices is called the n-cycle and usually denoted . It is also called a cyclic graph, a polygon or the n-gon. Special cases are the triangle , the square , and then several with Greek naming pentagon , hexagon , etc.
Friendship graphs edit
The friendship graph Fn can be constructed by joining n copies of the cycle graph C3 with a common vertex.[3]
Fullerene graphs edit
In graph theory, the term fullerene refers to any 3-regular, planar graph with all faces of size 5 or 6 (including the external face). It follows from Euler's polyhedron formula, (where indicate the number of vertices, edges, and faces), that there are exactly 12 pentagons in a fullerene and hexagons. Fullerene graphs are the Schlegel representations of the corresponding fullerene compounds.
-
20-fullerene (dodecahedral|dodecahedron|dodecahedral graph)
-
24-fullerene (hexagonal truncated trapezohedron graph)
-
26-fullerene
-
60-fullerene (truncated icosahedral graph)
-
70-fullerene
Platonic solids edit
The complete graph on four vertices forms the skeleton of the tetrahedron, and more generally the complete graphs form skeletons of simplices. The hypercube graphs are also skeletons of higher dimensional regular polytopes.
Truncated Platonic solids edit
Snarks edit
A snark is a bridgeless cubic graph that requires four colors in any edge coloring. The smallest snark is the Petersen graph, already listed above.
-
Loupekine snark (first)
-
Loupekine snark (second)
Star edit
A star Sk is the complete bipartite graph K1,k. The star S3 is called the claw graph.
Wheel edit
The wheel graph Wn is a graph on n vertices constructed by connecting a single vertex to every vertex in an (n-1)-cycle.
References edit
- ↑ Gallery initially copied here from the English Wikipedia en:Gallery of named graphs, started there by en:User:Arbor on 16 June 2006
- ↑ David Gries and Fred B. Schneider, A Logical Approach to Discrete Math, Springer, 1993, p 436.
- ↑ Gallian, J. A. "Dynamic Survey DS6: Graph Labeling." Electronic J. Combinatorics, DS6, 1-58, Jan. 3, 2007. [1].