New graph class links labeling to unweighted caterpillar tree structures
Pairwise Compatibility Graphs of Unweighted Caterpillars
Discrete Mathematics
Summary
Some graphs can be represented by linking their points using a special kind of tree called a caterpillar, where edges connected in a simple way matter. The authors show that understanding such graphs is the same as assigning numbers to nodes so that two nodes connect if their number difference lies in a certain range. This insight reveals properties of these graphs and how they relate to familiar shapes like cycles and grids but exclude others like certain stars or cubes. They also provide a way to decide if a graph can be represented this way quickly when the number range is fixed.
What this means in practice
- •For network designers: Identify network topologies that can be simplified using integer labeling methods reflecting caterpillar-like structures for efficient routing or analysis.
- •For software engineers: Use the polynomial-time test to verify if data structures can be represented by simplified caterpillar-based graphs, optimizing certain computations.
A theory result. No direct application yet.
Authors
Cyriac Antony, Manuel Lafond, Angelo Monti, Blerina Sinaimeri
Abstract
In this paper we study pairwise compatibility graphs whose witness tree is required to be an unweighted caterpillar. This is a natural restriction of PCGs, in the same line of research as the study of star witnesses, which led to the class of double-threshold graphs. In the caterpillar case, we show that this restriction is equivalent to a one-dimensional difference-labelling problem: a graph admits such a representation if and only if its vertices can be assigned integer labels so that adjacency is determined exactly by whether the absolute difference of two labels belongs to a given interval. Using this characterization, we derive structural properties of the class, including bounded twin-width, and study its relation with familiar graph families. We show that the class contains cycles and two-dimensional grids, while it excludes natural obstructions such as the subdivided star $S_{2,2,2,2,2}$, the cube graph $Q_3$, the wheel $W_6$, and the complement of the $3$-sunlet. We also consider restricted representations, including centipede witnesses and representations with a given interval and we give a polynomial-time recognition algorithm when the interval is fixed.