Zero-Distance Classes of Vertex-Labeled Graphs
Overview
Assigning nonnegative numbers to a connected graph's vertices gives a distance by taking the infimum, over connecting paths, of the largest number on each path. Distinct vertices can then have distance zero; sets of such mutually indistinguishable vertices are zero-distance classes. The paper characterizes which prescribed sets can be classes. It proves a finite-class version of Dovgoshey and Rovenska's cycle conjecture and disproves the unrestricted version by inserting a new vertex into every edge of the known halved Farey graph. In this counterexample at most three paths between any pair can have mutually disjoint interiors, and three is the smallest possible uniform bound. It also determines which graphs, under every labeling positive on at least one end of each edge, separate distinct vertices or make every point isolated.
Original public questions
Dovgoshey–Rovenska Conjectures 4.3 and 4.5, and Problem 4.4
Oleksiy Dovgoshey and Olga Rovenska: The Gomory–Hu inequality and trees — arXiv 2604.18400v1, pages 16–17: Conjecture 4.5 (counterexample and finite-class version), Conjecture 4.3 (proved) and Problem 4.4 (a vertex-label realization of the known recurrence criterion).
Original abstract (English)
A nonnegative vertex labeling of a connected graph defines a pseudoultrametric by minimizing the largest label along a path. Positive labels on at least one endpoint of each edge need not prevent distinct vertices from having distance zero. We characterize prescribed zero-distance classes by decreasing connected vertex sets. For finite classes this becomes connectivity of a finite auxiliary graph; for classes with countable complement it becomes connectivity after every finite deletion outside the class. The finite-class criterion gives a precise restricted version of a conjecture of Dovgoshey and Rovenska. The unrestricted conjecture is false: a labeling of the subdivided halved Farey graph collapses all its original vertices, although every pair has at most three internally disjoint paths. The bound three is optimal. We also realize infinite edge-connectivity classes by subdivision labelings, identify a compact metric quotient of the counterexample, and relate universal separation to the known criterion based on vertices that recur along a path sequence.
Mathematical review
Paper Close marks a working paper prepared and internally reviewed before release. Please treat it as an ordinary scholarly preprint: further checking or discussion may lead to corrections. It does not indicate complete formal verification or external peer review.
Review standard