Graph Theory in Networks

A graph model of a network

A telecommunication network can be represented as a set of points connected by relationships. Graph theory provides formal concepts and tools for describing, analyzing, and optimizing such networks. A graph representation allows mathematical principles to be applied to problems involving routing, reliability, and efficiency.

Elements of a graph

Every network graph consists of two basic components:

Vertex (or node): A point in the network. This can represent a computer, a router, a switch, or a telephone exchange.
Edge (or link): A connection between two vertices. This represents a physical communication link, such as a fiber-optic cable, a copper wire, or a wireless connection.

Graphs can be (if traffic flows only one way) or (if traffic can flow in both directions).

Graph properties and network characteristics

Analyzing graph properties describes the structure and selected characteristics of the represented network.

Graph degree

In an undirected graph, the of a vertex is the number of its direct connections. The minimum ( $\delta(G)$ ) and maximum ( $\Delta(G)$ ) degrees identify the least and most connected nodes. These values help identify potential bottlenecks and single points of failure.

Special graph types

Regular graph: A graph where every vertex has the same degree. This represents a network with a balanced and predictable structure. A 3-regular graph is called a cubic graph.
Complete graph ( $K_n$ ): A graph where every pair of vertices is connected by an edge. This represents a fully meshed network with redundant paths. The number of required edges is $\frac{n(n-1)}{2}$ , so the connection cost is high for large $n$ .
Planar graph: A graph that can be drawn on a plane without edges crossing. This concept is relevant to the physical layout of circuits and some network diagrams. Every complete graph $K_n$ with $n \ge 5$ is non-planar.

Paths and network resilience

A network needs paths that carry data from a source to a destination. The number and type of available paths affect its resilience to failures.

Edge-disjoint paths: These are at least two paths between the same start and end nodes that share no edges or links. Two such paths preserve connectivity between the endpoints after one link failure, such as a cut cable.
Vertex-disjoint paths: These are paths that share only their start and end nodes, with no common intermediary nodes or links. Two such paths preserve connectivity after one intermediary node fails, such as a router.
Graph connectivity: This is a measure of network resilience. ( $\kappa'(G)$ ) is the minimum number of links whose removal disconnects the graph. ( $\kappa(G)$ ) is the minimum number of nodes whose removal disconnects the graph. For a connected undirected graph, these values satisfy the inequality: $\kappa(G) \leq \kappa'(G) \leq \delta(G)$ .

Classic graph problems in networking

Many network design tasks correspond to problems known from graph theory.

Minimum spanning tree (MST): The goal is to find a subset of edges that connects all vertices in a connected without creating cycles and with the minimum possible total edge weight.
This applies to designing a backbone that connects cities or data centers with the minimum total edge weight. Prim's algorithm and Kruskal's algorithm are two standard methods for finding an MST.
Traveling Salesman Problem (TSP) and Hamiltonian cycle: TSP seeks the shortest route in a weighted graph that visits every vertex exactly once and returns to the origin. In network design, especially for ring and mesh networks, this closed route is a .
This problem arises in network topology design, particularly for ring networks, where the goal is to connect all nodes in a loop with the minimum total cable length.