Matchings and Independence in Bounded-Occupancy Token Graphs
Overview
Configurations place a fixed number of indistinguishable tokens on graph vertices; one move transfers one token along one edge. With unrestricted occupancy or a common even occupancy bound, if a bipartite base graph has disjoint edges covering one part, the configurations with even total occupancy on that part form a maximum independent set: no one-step move joins two of them, and no larger set has that property. This proves the supertoken independence conjecture. The paper also gives sufficient conditions for unequal vertex capacities and explicit odd-capacity counterexamples.
Original abstract (English)
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.
Mathematical review
The manuscript has completed internal review. Complete formalization is not yet established for this public version.
Review standard