Graph Glossary

Parts of a graph

Component

In an undirected graph, a connected subgraph that is not part of a larger connected subgraph.

Circuit

A trail in which the first and last vertices are equal. In contrast to the cycle, any vertex can be repeated.

Cycle

A trail in which only the first and last vertices are equal. Except for the tails and in contrast to the circuit, vertices cannot be repeated.

Euler circuit

A circuit that visits every edge of the graph.

Euler trail

A trail that visits every edge of the graph.

Flow

An example of a flow is a heat diffusion process across a graph. In such processes, each vertex starts with a certain amount of heat and, at each time point, exchanges heat with its neighbors (gains heat from its hotter neighbors; loses it to its colder neighbors).

Module

A subgraph whose vertices are densely connected to each other, and loosely to the rest of the graph.

Orientation

An orientation of an undirected graph is the directed graph resulting of assigning a direction to each of its vertices. A directed graph is oriented if no two vertices form a 2-cycle.

Path

A walk with no repeated vertices.

Spanning graph

A subgraph \(G' = (V', E')\) of \(G = (V, E)\) is spanning if \(V' = V\).

Subgraph

A graph resulting from subsetting vertices from a larger graph, as well as a subset of the edges connecting them.

Induced subgraph

A subgraph containing all the edges connecting the vertices in the original graph.

Trail

A walk with no repeated edges.

Triplet

A set of 3 vertices and at least 2 edges between them, none of which are redundant or loops. Open triplets have exactly 2 edges; closed triplets have exactly 3.

Walk

A walk on a graph is an alternating sequence of vertices and edges, such that every vertex is incident with the previous and the following edge (if any).

Properties of vertices

Adjacency

A vertex is adjacent with another vertex if they are connected by an edge. \(u \sim v\) denote that \(u\) and \(v\) are adjacent.

Degree

The degree of a vertex in a (simple) undirected graph is the number of edges incident with that vertex. In a (simple) directed graph we distinguish the indegree (number of edges with the vertex as their destination) and the outdegree (number of edges with the vertex as their source).

Destination

In a directed graph, the destination of an edge is the vertex at the head of the edge.

Distance

The distance between two vertices is the shortest path between them.

Hub

A vertex with a high degree.

Neighborhood

The neighborhood of vertex \(v\) is the induced subgraph containing all the vertices adjacent to \(v\).

Incidence

A vertex is incident with an edge if the vertex is one of the two vertices the edge connects.

Source

In a directed graph, the source of an edge is the vertex at the tail of the edge.

Types of graphs

Acyclical graph

A graph without cycles.

Bipartite graph

A acyclical graph whose vertices can be divided into two sets such that no pair of vertices in the same set are adjacent. Often, each of these sets are referred to as colors, and so we say that “there is no edge between two vertices of the same color.”

Complete graph

A simple, undirected graph in which every pair of vertices are connected by an edge. Complete graph are usually denoted by letter \(K\) with a subindex that indicates the total number of vertices. For instance, \(K_6\) represents the complete graph with 6 vertices.

Connected graph

A graph in which a path exists between every pair of vertices.

Digraph

A directed graph.

Directed graph

See Introduction to Graphs.

Forest

An undirected graph in which any two vertices are connected by at most one path. That is, a disjoint union of trees.

Multigraph

A graph which can have multiple edges between the same pair of vertices.

Regular

A graph in which every vertex has the same degree.

Simple graph

A graph with at most one edge between any pair of vertices and no loops.

Tree

An undirected graph in which there is only one path between every pair of nodes.

Triangle graph

A triplet with 3 edges. It consists of three closed triplets, each centered around each of the vertices.

Undirected graph

See Introduction to Graphs.

Spectral graph theory

First k eigenvectors

Eigenvectors associated with the k smallest eigenvalues.