頂点ラベル付きグラフの零距離同値類
Zero-Distance Classes of Vertex-Labeled Graphs
研究概要
連結グラフの頂点に非負の数を付け、二点を結ぶ各経路上の最大値について、全経路にわたる下限を取ると距離が定まる。異なる頂点間でも距離がゼロになり得る。この距離で互いに区別できない頂点の集合が零距離同値類である。本論文は指定した集合がこのような同値類となる条件を与える。Dovgoshey と Rovenska の閉路予想を有限同値類の場合に証明し、既知の半 Farey グラフの各辺に新しい頂点を一つ挿入することで、制限のない予想には反例を与える。この反例では、任意の二点間で内部頂点が互いに重ならない経路は高々三本であり、三は可能な最小の一様上界である。さらに、各辺の少なくとも一端に正の値を付けるすべてのラベル付けについて、異なる頂点が分離されるグラフと、各点が孤立点になるグラフを特徴付ける。
原文要旨（英語）
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.
数学の検証
原稿は内部レビューを完了しています。この公開版の完全な形式化は、まだ確立されていません。
検証基準