Graph Glossary
Parts of a graph
Component
In an undirected graph, a connected subgraph that is not part of a larger connected subgraph.
Cycle
A trail in which only the first and last vertices are equal.
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
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.
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
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.
Complete graph
A simple, undirected graph in which every pair of vertices are connected by an edge.
Connected graph
A graph in which a path exists between every pair of vertices.
Digraph
A directed graph.
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.
Triangle graph
A triplet with 3 edges. It consists of three closed triplets, each centered around each of the vertices.
Spectral graph theory
First k eigenvectors
Eigenvectors associated with the k smallest eigenvalues.