Computer scientists are constantly searching for ways to squeeze ever more bandwidth from communications networks.
Now a new approach to understanding a basic concept in graph theory, known as “vertex connectivity,” could ultimately lead to communications protocols — the rules that govern how digital messages are exchanged — that coax as much bandwidth as possible from networks.
Graph theory plays a central role in mathematics and computer science, and is used to describe the relationship between different objects. Each graph consists of a number of nodes, or vertices, which represent the objects, and connecting lines between them, known as edges, which signify the relationships between them. A communications network, for example, can be represented as a graph with each node in the network being one vertex, and a connection between two nodes depicted as an edge.
One of the fundamental concepts within graph theory is connectivity, which has two variants: edge connectivity and vertex connectivity. These are numbers that determine how many lines or nodes would have to be removed from a given graph to disconnect it. The lower the edge-connectivity or vertex-connectivity number of a graph, therefore, the easier it is to disconnect, or break apart.