Crab Research
返回结果列表
组合数学

圆柱图的四部分多重集分辨划分

Four-Part Multiset Resolutions of Cylindrical Graphs

工作论文 · Zenodo首次公开 修订

形式化是机器可检查的证明。证明助手的逻辑核心称为内核;它仅从已列明的基本逻辑原则出发,检查全部承重定理,不额外假设未经证明的定理。这称为 Kernel-Only 验证。

研究概述

记录顶点到各划分部分的最小距离,不保留部分标签,但保留重复距离。将两条同长的环在对应顶点之间连边所得的棱柱图,在环长至少为十时,四个部分足以区分所有顶点,而且已达最优。显式的环上距离多重集还给出指定圆柱图划分的精确高度边界。五部分上界适用于环长八、九的棱柱图,以及层数至少二、偶数周长至少十二的圆柱图。

原始公开问题

棱柱图:定理 3.5 中的多重集划分维数上界

Azzah Albejani, Yuqing Lin, Joe Ryan and Kiki A. Sugeng: Multiset Partition Dimension of Graphs — arXiv 2607.07407v3, page 16, Theorem 3.5: the prism upper bound is improved to the optimal value four for cycle lengths at least ten. The equality-six conjecture from v1 is absent from v3; the general Problem 1 is not claimed solved.

原文摘要(英文)

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.

公开摘要来源

multiset partition dimensioncylindrical graphsprism graphsresolving partitionsmultiset dimension

数学审核

Kernel-Only

主要结论拥有公开的内核检查证明包,并已审核其与论文的对应关系。这与外部同行评审是不同的验证。

审核标准
返回结果列表
返回 数学