Glossary of graph theoretic terms

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

A

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 .

$n$-arc

A walk of n  vertices where any repeated vertices are three or more steps apart.

$n$-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

The biclique $K_{3,5}$.

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 $K_{3,5}$.

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

Claw

The star graph $S_{3}$.

Clique

A complete subgraph.

$C_{n}$

The cyclic graph with n  vertices.

The complete graph $K_{7}$.

Complete graph

A graph where every pair of its vertices is an edge.

Complete $k$-partite graph

A k -partite graph where every pair of vertices in different parts is an edge.

Connected graph

Main article: Connectivity § Graphs

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

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

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

Flag

Main article: 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

Main article: 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

Girth

The size of the smallest cycle of a graph.

I

Incident

An edge $(v_{1},v_{2})$ is incident on v₁  and v₂  and no other vertices.

K

$K_{n}$

The complete graph with n  vertices.

$K_{n,m}$

The biclique with with parts of size n  and m .

L

Loop

An edge $(u,v)$ where $u=v$. Graphs with loops are not simple.

M

Multiple edge

More than one edge between the same two vertices.

P

Part

One of the sets of vertices in a k -partite graph with no internal connections.

$k$-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

$Q_{n}$

The skeleton of the rank-n  hypercube.

R

Regular graph

A graph in which every vertex has the same degree.

S

The star graphs $S_{3},S_{4},S_{5},S_{6}$.

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.

$S_{n}$

A star graph with $n+1$ vertices.

Star graph

A complete bipartite graph in which one of the parts has one vertex. The star graph with $n+1$ vertices is denoted $S_{n}$. Alternatively, $S_{n}=K_{1,n}$.

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

Trail

A walk in which all edges are distinct.

V

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

Walk

A sequence of edges, $\{e\}_{i}$, and a sequence of vertices, $\{v\}_{i+1}$, of a graph, such that $e_{i}=(v_{i},v_{i+1})$.

External links

• Wikipedia contributors. "Glossary of graph theory".