Glossary of graph theoretic terms

This page provides a reference for graph theory related terms that may appear on this wiki.

A Edit

Adjacent
Two vertices, u  and v , are adjacent in a graph if (u , v ) is an edge in that graph. Alternatively there is an edge incident on both u  and v .
 -arc
A walk of n  vertices where any repeated vertices are three or more steps apart.
 -arc-transitive graph
A graph whose automorphism group acts transitively on n -arcs. 1-arc-transitive graphs are also called flag-transitive.
Articulation point
A vertex of a connected graph which when removed along with all incident edges causes the graph to become disconnected.

B Edit

 
The biclique  .
Biclique
A bipartite graph with two parts A  and B , such that every vertex in A  is adjacent to every vertex in B . If A  has n  vertices and B  has m  vertices then the biclique is denoted  .
Bipartite
A graph with two sets of vertices A  and B , called parts, such that no vertex in A  is adjacent to a vertex in A , and no vertex in B  is adjacent to a vertex in B . Alternatively a graph with a vertex 2-coloring.
Buckle
See § loop

C Edit

Claw
The star graph  .
Clique
A complete subgraph.
 
The cyclic graph with n  vertices.
 
The complete graph  .
Complete graph
A graph where every pair of its vertices is an edge.
Complete  -partite graph
A k -partite graph where every pair of vertices in different parts is an edge.
Connected graph
A graph is connected iff there is a path between every pair of vertices.
Cubic graph
A regular graph with vertex degree 3.
Cycle
A non-empty trail with an equal start and end vertex. Two cycles are generally considered the same if they have the same vertices regardless of where they start or end.
Cyclic graph
A graph with exactly one cycle consisting of all of its vertices and edges

D Edit

Degree
The number of edges incident on a vertex is the degree of that vertex.
Disconnected graph
A graph which is not connected
Distance
The distance between two vertices in a graph is the length of the shortest path beginning at one and ending at the other.
Distance-transitive graph
A graph such that for any constant d  its automorphism group acts transitively on pairs of vertices, which are distance d  apart. Distance-transitive graphs have a high degree of symmetry, they are flag-transitive, vertex-transitive, edge-transitive, etc.

E Edit

Edge
One of the two basic elements of a graph. Edges connect vertices. In a simple graph edges are typically represented as an unordered pair of vertices.
Edge-colored graph
A graph with labeled edgeses such that if two edges are incident on a vertex they have different labels. A graph is n -edge-colored if its label set has size n .

F Edit

Flag
A vertex-edge pair (v , e ) where v  is one of the vertices of e . This is a special case of the flags of a poset for graphs and is analogous to the concept of flags on polytopes.
Flag graph
An edge-colored graph with vertices corresponding to the flags of a polytope.

Flag-transitive graph
A graph whose automorphism group acts transitively on its flags. This is analogous to the concept of abstract regular polytopes. However, unlike a regular polytope where the automorpism group and the flags set must have the same size, flag-transitive graph may have symmetry exceeding the number of automorphisms.

G Edit

Girth
The size of the smallest cycle of a graph.

I Edit

Incident
An edge   is incident on v1  and v2  and no other vertices.

K Edit

 
The complete graph with n  vertices.
 
The biclique with with parts of size n  and m .

L Edit

Loop
An edge   where  . Graphs with loops are not simple.

M Edit

Multiple edge
More than one edge between the same two vertices.

P Edit

Part
One of the sets of vertices in a k -partite graph with no internal connections.
 -partite
A graph with k  sets of vertices, called parts, such that no vertex is adjacent to any vertex in the same part. Alternatively a graph with a vertex k -coloring.
Path
A walk in which all vertices are distinct. A path is also a trail.
Properly edge-colored graph
An n -edge-colored graph which is also n -regular.

Q Edit

 
The skeleton of the rank-n  hypercube.

R Edit

Regular graph
A graph in which every vertex has the same degree.

S Edit

 
The star graphs  .
Self-loop
See § loop
Simple graph
A simple graph is an undirected graph with at most 1 edge between and two vertices and no loops. In some context all graphs are implied to be simple.
 
A star graph with   vertices.
Star graph
A complete bipartite graph in which one of the parts has one vertex. The star graph with   vertices is denoted  . Alternatively,  .
Subgraph
A subgraph of a graph G  is a graph formed from a subset of the vertices and edges of G . The subgraph must also be a valid graph so the endpoints of every edge must be included.
Symmetric graph
See § Flag-transitive graph

T Edit

Trail
A walk in which all edges are distinct.

V Edit

Vertex
One of the two basic elements of a graph. Vertices are connected by edges.
 
A 3-vertex coloring of the Petersen graph.
Vertex-colored graph
A graph with labeled vertices such that no two adjacent vertices share the same label. A graph is n -vertex-colored if its label set has size n .

W Edit

Walk
A sequence of edges,  , and a sequence of vertices,  , of a graph, such that  .

External links Edit