Crab Research
组合数学

占位有界筹码图中的匹配与独立数

Matchings and Independence in Bounded-Occupancy Token Graphs

Alex Chengyu Li

工作论文 · Zenodo首次公开

研究概述

构型把固定数量的不可区分筹码放在图的顶点上,每步沿一条边移动一个筹码。在不限占位数或采用统一偶数占位上限时,若二部底图有一组端点不交的边覆盖某一侧的全部顶点,则该侧占位总数为偶数的构型组成最大独立集:它们之间没有一步合法移动,也不存在更大的、具有这一性质的构型集合。这证明了超筹码图独立数猜想。论文还给出不同顶点容量下的充分条件,以及奇数容量的显式反例。

原文摘要(英文)

A token configuration assigns nonnegative occupancies of total size k to the vertices of a graph; a move transfers one token along one edge. We prove the independence-number conjecture of Reyes, Dalfó and Fiol for these graphs with unrestricted occupancy. If a bipartite base graph has a matching saturating one part, its token graph has a matching saturating every configuration with odd occupancy on that part. The even configurations therefore form a maximum independent set. The same conclusion holds for every even finite occupancy bound. A decomposition into products of paths gives sharp matching and independence bounds for arbitrary hosts and a sufficient condition for unequal vertex capacities, with a complete classification of the relevant two-vertex condition. For every odd finite capacity we exhibit a bipartite host whose token graph has an independent set larger than both parity classes. We also obtain exact Shannon capacities in the saturated cases and asymptotic matching densities as the number of tokens grows.

公开摘要来源

token graphssupertoken graphsmatchingsindependence numberbounded occupancyShannon capacity

数学审核

内部定稿

稿件已完成内部审核,当前公开版本尚未完成完整形式化。

审核标准
返回 数学