# Glossary of graph theoretic terms

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]

- 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.
- 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
- path between every pair of vertices. A graph is connected iff there is a
- 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
- 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. A
- Flag graph
- flags of a polytope. An edge-colored graph with vertices corresponding to the
- 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 v
_{1}and v_{2}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]

## 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]

## R[edit | edit source]

## S[edit | edit source]

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

- Wikipedia contributors. "Glossary of graph theory".