Graph distances bounded by packings and connectivity measures
Triameter, distance packings, and vertex connectivity
Discrete Mathematics
Summary
This work explores how certain distance measures in networks, called triameters, can be limited using tools known as distance packings and vertex connectivity. The authors establish precise formulas that show how these concepts relate and confirm an earlier prediction about graph distances. They also find which network shapes maximize these distances given certain connectivity constraints. Their approach involves simplifying complex networks into special forms that preserve key distance properties among selected points.
What this means in practice
- •For network designers: Assess upper limits on distance-based metrics in network topologies defined by connectivity requirements to improve robustness evaluations.
- •For graph algorithm engineers: Use tight bounds on distance packings and connectivity to optimize algorithms that rely on vertex distances for routing and fault tolerance.
A theory result. No direct application yet.
Authors
Artem Hak, Sergiy Kozerenko
Abstract
We study upper bounds for the triameter of a connected graph in terms of distance packings and vertex connectivity. For any positive integer $k$, we bound the triameter of a graph by a linear function of its $k$-packing number and show that this bound is tight for all values of the parameters. As a corollary, we confirm the conjecture of Das and Abdioğlu on the upper bound for the triameter in terms of the order and the minimum degree of a graph. We also find the maximum triameter among graphs with given order and vertex connectivity, and describe the extremal graphs. Our main tool is a projection of a graph onto a spider or a unicyclic graph which preserves the distances between three prescribed vertices.