Klinked

Klinked, usually written as k-linked, is a term used in graph theory to describe a robust connectivity property of a graph. A graph G is k-linked if for every choice of k pairs of distinct vertices (s1, t1), (s2, t2), ..., (sk, tk) there exist k vertex-disjoint paths P1, P2, ..., Pk such that Pi connects si to ti for each i. This definition makes k-linked graphs a strengthening of basic connectivity, focusing on simultaneously connecting multiple terminal pairs with nonoverlapping routes.

Relation to other concepts: The notion is closely tied to Menger’s theorem, which relates the maximum number of disjoint s–t paths to the size of minimum vertex cuts. In parallel, higher vertex-connectivity (being more than just connected) often implies stronger linkage properties: under certain conditions, enough connectivity guarantees the existence of disjoint s–t paths for multiple pairs, a property exploited in network routing and combinatorial constructions. The exact implications can depend on graph size, degree conditions, and other structural constraints.

Computational perspective: The k-linkage problem asks, given a graph and k pairs of terminals, whether there exist vertex-disjoint paths connecting each pair as required. For fixed k, algorithmic solutions exist with polynomial-time complexity; when k is part of the input, the problem becomes more challenging and is known to be NP-hard in general graphs, though fixed-parameter tractable approaches exist for some parameterizations.

Uses and scope: k-linked graphs are a topic of study in structural graph theory, with applications in network design, routing, and graph minor theory. The term is standard in mathematical literature and should not be confused with informal uses of “k-linked” in non-graph contexts.