Glossary of graph theory

Glossary of graph theory

Graph theory is a fun part of math that looks at how things are connected. It studies objects, called nodes or vertices, and how they are linked by edges. Edges are like lines or paths that connect the nodes.

Graphs help us solve many real-world problems. For example, they can show the quickest route on a map or help design strong networks for computers and phones. Using simple pictures with dots and lines, graph theory can solve tricky puzzles about connections and relationships.

This glossary explains important words and ideas in graph theory. Whether you are curious about how networks work or just love puzzles, graph theory offers fun and useful ways to think about the world.

Symbols

Square brackets [ ] are used to show a smaller part of a bigger graph, called an induced subgraph. For example, _G__S_ means a piece of a larger graph.

The prime symbol ' helps us talk about different parts of graphs. For example, _α_(G_) tells us about one part of a graph, while _α_′(G_) tells us about a related part of its [line graph.

A

In graph theory, an absorbing set is a group of points in a directed graph. Every other point has a connection leading to this set.

An acyclic graph has no cycles. For undirected graphs, this means it is a type of forest. In directed graphs, it is known as a directed acyclic graph.

The adjacency matrix shows connections between points in a graph. A 1 means there is a connection. A 0 means there is no connection.

Other terms like adjacent describe points or lines that connect directly. Alternating paths switch between connected and unconnected lines in matchings.

B

A bipartite graph is a graph where you can split the points into two groups. Points in one group only connect to points in the other group, not to others in their own group. These graphs cannot have cycles with an odd number of steps and can be colored using just two colors.

Other terms include biconnected. This describes a graph where there are at least two different paths between any two points. A bridge is an edge that, if removed, would break the graph into separate parts.

C

C_n is an n-vertex cycle graph.

A cactus graph is a connected graph where each edge is part of at most one cycle.

A cage is a regular graph with the smallest number of vertices for its size of cycles.

A canonical form of a graph is a special way to describe a graph so that two graphs with the same description are the same. Graph canonization is the process of finding this special description.

A graph made by removing one vertex from another graph is called a card, especially in the reconstruction conjecture.

Carving width is a way to measure the size of a graph, similar to branchwidth.

A caterpillar tree is a tree where the middle nodes form a line.

The center of a graph is the set of vertices that are closest to all other vertices, based on eccentricity.

In a tree that starts from one point, a child of a vertex v is a neighbor connected by an edge going out from v.

A chord of a cycle is an edge that connects two points on the cycle but is not part of the cycle.

Chromatic graph theory studies graph coloring. The chromatic number χ(G) is the smallest number of colors needed to color G so that no two connected points share the same color.

A graph is k-choosable if it can be colored using a list coloring when each point has a list of k possible colors.

A circle graph is the intersection graph of lines that cross a circle.

A circuit can mean a closed path or part of the cycle space. The circuit rank of a graph is the size of its cycle space.

The circumference of a graph is the length of its longest simple cycle.

A class of graphs is a group of graphs that share a certain property.

A claw is a tree with one middle point and three ends.

A clique is a set of points all connected to each other. The clique number ω(G) of a graph G is the size of its largest clique.

A connected component of a graph is a part of the graph where you can reach any point from any other point.

A connected graph is one where you can draw a path between any two points.

Edge contraction is an operation that removes an edge from a graph and merges the two points it connected.

The converse graph is another name for the transpose graph.

A k-core is the part of a graph left after removing all points with fewer than k connections.

A cube graph is the eight-point graph showing the vertices and edges of a cube.

A cut is a way to split the points of a graph into two groups, or the set of edges that connect these groups.

A cycle can be a type of graph or a path that starts and ends at the same point without repeating points or edges. Special types of cycles include Hamiltonian cycles and the shortest cycle, which determines the girth of a graph. A k-cycle is a cycle with k points. A cycle graph is a graph that is itself a simple cycle.

D

A directed acyclic graph (or DAG) is a special type of graph. It has directions, but it never loops back on itself directed acyclic graph.

Other important words in graph theory include:

• Deck: This is a set of graphs made by taking away one point at a time from a bigger graph. It helps us study how well we can figure out the original graph reconstruction conjecture.
• Degeneracy: This tells us how "complex" a graph is. A graph is k-degenerate if every small part of it has at most k connections from each point degeneracy.
• Degree: This counts how many connections a point has. The degree of a graph is the most connections any single point has handshaking lemma.
• Density: This measures how many connections there are compared to the most possible. A dense graph has many connections, while a sparse graph has few dense graph.
• Diameter: This is the longest shortest path between any two points in a connected graph diameter.
• Diamond graph: A small graph with four points and five connections diamond graph.
• Digraph: Short for directed graph, where each connection has a specific direction directed graph.
• Distance: The fewest steps needed to go from one point to another in a graph distance.
• Dominating set: A group of points where every other point is either in the group or directly connected to someone in the group dominating set.
• Dual graph: For a graph drawn on a plane, the dual graph has a point for each space between lines dual graph.

E

E

E(G) is the edge set of G; see edge set.

In graph theory, an ear of a graph is a path where the ends may be the same, but no other points repeat. An ear decomposition breaks down the edges of a graph into a sequence of these ears.

The eccentricity of a vertex tells us how far it is from the most distant vertex in the graph.

An edge is one of the main parts of a graph, connecting two vertices. Edges can go in one direction or both directions.

An edge cut is a group of edges that, if removed, would split the graph apart. A single edge that does this is called a bridge.

The edge set is simply all the edges in a graph.

An edgeless graph is a graph with no edges at all — just vertices standing alone.

A graph embedding shows a graph as points (vertices) and curves (edges) in space, without any curves crossing. A planar graph can be drawn on a flat surface, while a toroidal graph can be drawn on a donut shape.

The empty graph has either just vertices with no edges, or no vertices and no edges at all.

An endpoint is one of the vertices where an edge starts or ends. For a directed edge, the starting point is called the tail, and the ending point is the head.

Graph enumeration is about counting different kinds of graphs or structures within graphs.

An Eulerian path is a path that uses every edge of a graph exactly once. If it starts and ends at the same vertex, it’s called an Eulerian circuit.

An even number is divisible by two — for example, an even cycle has an even number of vertices.

An expander graph is a graph where spreading out its edges or vertices doesn’t shrink the graph too much.

F

In graph theory, a face is a part of a flat surface that is not covered by the lines of the graph. When we draw the graph on paper, most faces are surrounded by lines, but one special face goes out to infinity. This is called the outer face.

A factor of a graph is a smaller graph that includes all the points (vertices) of the original graph. Special types of factors have names based on how many connections (edges) each point has. For example, a 1-factor pairs up all the points so each point connects to exactly one other point.

G

G

This letter is often used to represent a graph.

genus

The genus of a graph tells us the simplest surface needed to draw the graph without any edges crossing.

geodesic

A geodesic is another name for the shortest path between two points in a graph.

giant

In studies of random graphs, a giant component is a large connected part that includes a steady portion of all the points in the graph.

girth

The girth of a graph is the number of steps in its smallest loop.

graph

A graph is the main object studied in graph theory. It consists of points, called vertices, connected by lines, called edges. Graphs can be directed, where edges have a direction, or undirected, where they do not. Mixed graphs have both types of edges.

greedy

A greedy algorithm makes the best choice at each step. For example, a greedy coloring of a graph assigns the first available color to each vertex in order.

Grötzsch

1. Herbert Grötzsch
2. The Grötzsch graph, a special graph that has no triangles but still needs four colors to color it properly.
3. Grötzsch's theorem shows that triangle-free planar graphs can always be colored using only three colors.

Grundy number

The Grundy number of a graph is the most colors you might need when coloring it using a greedy method, depending on the order you choose the vertices.

H

H

H stands for a graph, especially when another graph is called G.

H-coloring

An H-coloring of a graph G (where H is also a graph) is a special way to match H to G.

H-free

A graph is H-free if it does not have a smaller graph H inside it. For example, triangle-free graphs are graphs that do not have a triangle graph inside them.

Hadwiger

1. Hugo Hadwiger
2. The Hadwiger number of a graph is the size of the largest complete minor of the graph.
3. The Hadwiger conjecture suggests that the Hadwiger number is never smaller than the chromatic number.

Hamiltonian

A Hamiltonian path or Hamiltonian cycle is a path or cycle that visits each vertex in the graph exactly once. A graph is Hamiltonian if it contains a Hamiltonian cycle, and traceable if it contains a Hamiltonian path.

haven

A k-haven is a special tool used to study how graphs are built.

height

The height of a node in a tree is the number of edges in the longest path from that node to a leaf. The height of a tree is the height of its root node.

hereditary

A hereditary property of graphs is a property that stays true for all smaller parts of the graph.

hexagon

A simple cycle with exactly six edges and six vertices.

hole

A hole is a special cycle in a graph with four or more vertices. This idea is important in the study of perfect graphs, described by the strong perfect graph theorem. Hole-free graphs are the same as chordal graphs.

homomorphic equivalence

Two graphs are homomorphically equivalent if there are special ways to match them.

homomorphism

A graph homomorphism is a way to match the vertices of two graphs while keeping their connections. It is used in many graph theory studies.

hyperarc

A directed hyperedge with a starting point and an ending set.

hyperedge

An edge in a hypergraph, which can connect to more than two points, unlike normal graph edges.

hypercube

A hypercube graph is a graph made from the vertices and edges of a geometric hypercube.

hypergraph

A hypergraph is a more general type of graph where edges can connect to more than two points.

hypo-

This prefix describes a graph that lacks a certain property, but becomes true when any single vertex is removed. For example, a hypohamiltonian graph does not have a Hamiltonian cycle, but removing any one vertex makes it have one.

I

The "in-degree" of a directed graph counts how many edges point toward each vertex. An "incidence" describes a vertex connected to an edge.

An "incidence matrix" is a table that shows which vertices connect to which edges, using ones and zeros. An "independent set" is a group of vertices with no edges between them.

An "induced subgraph" includes all edges between a chosen group of vertices. An "infinite graph" has endless vertices or edges.

An "isolated vertex" has no edges connected to it at all. Two graphs are "isomorphic" if they have the same structure, just arranged differently.

J

The join of two graphs is made by connecting every point, or vertex, from one graph to every point in the other graph. You do this by putting the two graphs apart from each other, and then linking each point in one graph to each point in the other graph.

K

K

The notation K is used to name special types of graphs called complete graphs, complete bipartite graphs, and complete multipartite graphs. You can learn more about complete graphs here.

κ

κ(G), using the Greek letter kappa, can mean two things. It might refer to the vertex connectivity of a graph G, or it could show the clique number of G. You can find out more about vertex connectivity here and clique numbers here.

kernel

In a directed graph, a kernel is a special group of points that is both stable and absorbing.

knot

A knot in graph theory is a tricky part of a directed graph. To learn more, you can explore knot (mathematics) and knot theory.

L

L

L(G) is the line graph of G; see line.

label

A labeled graph is a graph whose points or lines have labels. The terms vertex-labeled or edge-labeled may be used to say which parts of a graph have labels. Graph labeling talks about giving labels to graphs with certain rules. See also graph coloring.

leaf

A leaf vertex or pendant vertex (especially in a tree) is a point with only one connection. A leaf edge or pendant edge is the line that connects a leaf vertex to its one neighbour.

length

In a graph with no weights, the length of a circle, path, or walk is the number of lines it uses. In a graph with weights, it may be the total of the weights of the lines it uses. Length helps us find the shortest path, girth (shortest circle length), and longest path between two points in a graph.

level

A node's level in a rooted tree is how many points are in the path from the root to the node. For example, the root has level 1 and any one of its nearby points has level 2.

line

This means an undirected edge. The line graph L(G) of a graph G is a graph with a point for each edge of G and a line for each pair of edges that share a point in G.

linkage

This is another name for degeneracy.

list

An adjacency list is a way computers show graphs for use in graph programs.

local

A local property of a graph is a property that depends only on the neighbourhoods of the points in the graph.

loop

A loop or self-loop is a line where both ends are the same point. It makes a circle of length 1. These are not allowed in simple graphs.

M

In graph theory, a matching is a set of connections where no two share a point. A perfect matching links every point, and a maximum matching uses as many connections as possible.

A minor of a graph is made by removing points or connections. Other terms like modular graph and multigraph describe special kinds of graphs.

N

A neighbor or neighbour is a point that is directly joined to another point in a graph. The neighborhood of a point includes all the points directly joined to it. In graph theory, a lower-case n is often used to show the number of points in a graph. A network is a type of graph where extra details, like names, are linked to the points or connections. A node is another name for a point. A non-edge is a pair of points that are not joined together. A null graph is the same as an empty graph, which has no points or lines at all.

A triangle is a cycle with three points. A trivial graph has either no points or just one point.

Turán graphs are special graphs with the most lines possible without certain cycles.

U

In graph theory, a unary vertex is a vertex in a tree that has exactly one child vertex.

An undirected graph is a graph where the edges do not have a direction. This means the two points connected by an edge are the same, no matter which way you look at it. A universal graph is a special graph that contains every possible smaller graph. A universal vertex is a vertex connected to every other vertex in the graph. An unweighted graph is a graph where the points and lines do not have numbers or "weights" assigned to them. The utility graph is a special type of graph known as a complete bipartite graph, often written as K_3,3.

V

See vertex set.

valency

This is another word for degree.

vertex

A vertex (more than one are called vertices) is one of the main parts, along with edges, that make up graphs. Vertices are usually simple points.

vertex cut

separating set

This is a group of vertices that, if taken away, can break apart the graph. A single-vertex cut is called an articulation point or cut vertex.

vertex set

This is the group of vertices in a graph G, sometimes written as V(G).

vertices

See vertex.

Vizing

1.  Vadim G. Vizing 2.  Vizing's theorem about the chromatic index. 3.  Vizing's conjecture on graph domination numbers.

volume

This is the total of the degrees of a group of vertices.

W

The letter W is used in notation for wheel graphs and windmill graphs.

Wagner refers to several ideas in graph theory:

1. Klaus Wagner, a mathematician who helped develop the field.
2. The Wagner graph, a special graph with eight points.
3. Wagner's theorem, which describes planar graphs.

A walk is a path that moves through a series of edges connecting vertices. Walks can be open (starting and ending at different points) or closed (starting and ending at the same point).

In graph theory, weight means a number given to a vertex or edge. A weighted graph is one where these points or lines have weights.

A wheel graph is made by adding a central point, called a universal vertex, to a simple circle of points.

A windmill graph is formed by combining several groups of points (called cliques) that all share one common point.