Glossary of graph theoretic terms

From Polytope Wiki
Revision as of 16:38, 17 February 2024 by Sycamore916 (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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

A[edit | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

Girth
The size of the smallest cycle of a graph.

I[edit | edit source]

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

K[edit | edit source]

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

L[edit | edit source]

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

M[edit | edit source]

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

P[edit | edit source]

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 | edit source]

The skeleton of the rank-n  hypercube.

R[edit | edit source]

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

S[edit | edit source]

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 | edit source]

Trail
A walk in which all edges are distinct.

V[edit | edit source]

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 | edit source]

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

External links[edit | edit source]