Results on Cartesian $1$-capacity of graphs

The concept of graph capacity extends graph span by considering the maximum number of agents that can simultaneously traverse a graph while preserving a prescribed minimum distance.

We study the Cartesian $1$-capacity, corresponding to the movement in which exactly one agent moves at each step.

We establish general lower and upper bounds based on structural graph properties and derive exact results for trees.

Our work highlights the role of branching and bridge structures in determining the Cartesian $1$-capacity and provides new insights into collision-free multi-agent motion on graphs.