圆柱图的四部分多重集分辨划分
Four-Part Multiset Resolutions of Cylindrical Graphs
研究概述
记录顶点到各划分部分的最小距离,不保留部分标签,但保留重复距离。将两条同长的环在对应顶点之间连边所得的棱柱图,在环长至少为十时,四个部分足以区分所有顶点,而且已达最优。显式的环上距离多重集还给出指定圆柱图划分的精确高度边界。五部分上界适用于环长八、九的棱柱图,以及层数至少二、偶数周长至少十二的圆柱图。
原文摘要(英文)
A multiset resolving partition distinguishes each vertex of a graph by the unordered multiset of its minimum distances to the partition parts. We prove that every prism formed from two corresponding cycles of length at least ten has multiset partition dimension four, using two singleton parts, one vertical pair and one residual part. Five parts suffice for cycle lengths eight and nine. More generally, we construct optimal four-part partitions of cylindrical graphs using three singleton landmarks in an end cycle and one residual part. For a family of near-antipodal landmark triples, we determine the exact number of layers at which the specified construction first fails. This number is one more than the least positive translation relating two cycle distance profiles, which we compute for odd and even circumferences with explicit collision witnesses. General transfer criteria account for the extra comparisons introduced at landmark vertices. Combining the bipartite criterion with an existing four-landmark theorem also gives a five-part upper bound at every height of at least two for even circumferences of at least twelve. The three-landmark cylinder families have ordinary multiset dimension three.
数学审核
稿件已完成内部审核,当前公开版本尚未完成完整形式化。
审核标准