# Graphs in graph theory

**English:**Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer. A famous example is the Petersen graph, a concrete graph on 10 vertices that appears as a minimal example or counterexample in many different contexts.

^{[1]}

## Contents

## Individual graphsEdit

## Highly symmetric graphsEdit

### Strongly regular graphsEdit

The strongly regular graph on *v* vertices and rank *k* is usually denoted srg(*v,k*,λ,μ).

Paley graph of order 13

### Symmetric graphsEdit

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 graphsEdit

## Graph familiesEdit

### Complete graphsEdit

The complete graph on vertices is often called the * -clique* and usually denoted , from German *komplett*.^{[2]}

### Complete bipartite graphsEdit

The complete bipartite graph is usually denoted . The graph equals the 4-cycle (the square) introduced below.

, the utility graph

### CyclesEdit

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 graphsEdit

The friendship graph *F _{n}* can be constructed by joining

*n*copies of the cycle graph

*C*

_{3}with a common vertex.

^{[3]}

### Fullerene graphsEdit

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)

60-fullerene (truncated icosahedral graph)

### Platonic solidsEdit

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.

Cube

,

### Truncated Platonic solidsEdit

### SnarksEdit

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.

### StarEdit

A star *S*_{k} is the complete bipartite graph *K*_{1,k}. The star *S*_{3} is called the claw graph.

### WheelEdit

The wheel graph *W _{n}* is a graph on

*n*vertices constructed by connecting a single vertex to every vertex in an (

*n*-1)-cycle.

## ReferencesEdit

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