Span capacities of graphs

Aljo\v{s}a \v{S}uba\v{s}i\'c; Andrej Taranenko; Christopher Mouron; Mateja Gra\v{s}i\v{c}; Tanja Vojkovi\'c

arxiv: 2605.16852 · v1 · pith:BEDPAEP3new · submitted 2026-05-16 · 🧮 math.CO

Span capacities of graphs

Mateja Gra\v{s}i\v{c} , Christopher Mouron , Aljo\v{s}a \v{S}uba\v{s}i\'c , Andrej Taranenko , Tanja Vojkovi\'c This is my paper

Pith reviewed 2026-05-19 20:46 UTC · model grok-4.3

classification 🧮 math.CO

keywords d-capacitytopfull graphsgraph factorizationconnectivitypathscyclesbipartite graphssimultaneous traversals

0 comments

The pith

The d-capacity counts the maximum players who can simultaneously traverse every vertex of a graph while staying at least d apart, reaching the theoretical maximum for d=1 exactly when the graph is topfull.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper defines the d-capacity of a graph as the largest number of players that can all visit every vertex at once while keeping a separation of at least d under chosen movement rules. It computes the exact values for paths and cycles and derives bounds for bipartite graphs. The central result characterizes topfull graphs as those that attain the highest possible 1-capacity and links this property to the existence of suitable factorizations together with adequate connectivity. A reader would care because these quantities give concrete limits on how many full-covering routes can run in parallel without violating distance constraints in networks or structures.

Core claim

The paper claims that a graph attains the theoretical maximum value of its 1-capacity if and only if it belongs to the class of topfull graphs, which are characterized by admitting factorizations that enable the maximum number of simultaneous traversals while preserving unit separation, and this characterization is tied directly to the connectivity properties of the graph.

What carries the argument

The d-capacity, defined as the maximum number of simultaneous full-vertex traversals that can be maintained with minimum distance d between any pair of players, with topfull graphs serving as the subclass that saturates the upper bound for d equal to 1 through factorizations and connectivity.

Load-bearing premise

The movement rules for players on the graph are assumed to permit a finite maximum number of simultaneous full traversals that can actually be attained for paths, cycles, bipartite graphs, and topfull graphs.

What would settle it

A single counterexample graph that reaches the theoretical maximum 1-capacity without satisfying the factorization or connectivity conditions used to define topfull graphs, or a topfull graph whose measured 1-capacity falls below that maximum, would refute the characterization.

Figures

Figures reproduced from arXiv: 2605.16852 by Aljo\v{s}a \v{S}uba\v{s}i\'c, Andrej Taranenko, Christopher Mouron, Mateja Gra\v{s}i\v{c}, Tanja Vojkovi\'c.

read the original abstract

The $d$-capacity of a graph $G$ is introduced as the maximum number of players that can simultaneously traverse $G$ such that each player visits all vertices while maintaining a distance of at least $d$ under various movement rules. We determine their values for paths and cycles and provide bounds for bipartite graphs. Furthermore, we characterize topfull graphs, where the 1-capacities reach their theoretical maximum, establishing a connection to graph factorizations and connectivity.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper introduces d-capacity as a new traversal parameter and gives exact values on paths and cycles plus a factorization link for topfull graphs.

read the letter

The key takeaway is that the authors define d-capacity as the largest number of players who can each visit every vertex of G while keeping pairwise distance at least d, and they compute this exactly for paths and cycles. They also characterize the graphs where the 1-capacity meets its obvious upper bound and connect that property to factorizations and connectivity. Those concrete numbers on the two simplest infinite families are the clearest new content. The factorization connection is a reasonable bridge to existing decomposition results, and if the arguments are self-contained they give a clean way to recognize when the capacity saturates. The bounds stated for bipartite graphs add a modest extension but look secondary. The main soft spot is the movement model. The abstract refers to “various movement rules” without spelling out whether steps are synchronous, whether players occupy vertices or edges, or how the distance condition is enforced at each time step. The stress-test note flags exactly this gap. If the full text supplies a precise combinatorial definition that makes the finite maximum well-defined and attainable on the families they study, the concern stays minor; otherwise the characterization of topfull graphs rests on an unstated modeling choice rather than a derived property. No obvious circularity or free parameters appear in the abstract claims. This is aimed at combinatorialists who track new graph parameters or who work on multi-agent routing problems on graphs. A reader already familiar with path decompositions or token sliding will see the most direct value. The exact results on paths and cycles plus the factorization link are enough to justify sending it to a referee, though the movement rules will need to be checked carefully in review.

Referee Report

2 major / 2 minor

Summary. The paper introduces the d-capacity of a graph G as the maximum number of players that can simultaneously traverse G such that each player visits all vertices while maintaining a distance of at least d under various movement rules. It determines their values for paths and cycles and provides bounds for bipartite graphs. Furthermore, it characterizes topfull graphs, where the 1-capacities reach their theoretical maximum, establishing a connection to graph factorizations and connectivity.

Significance. If the movement rules are rigorously formalized and the characterizations proven, the work contributes concrete values for basic classes and links a new traversal capacity to factorization theory, which may be of interest in combinatorial optimization. The results for paths and cycles offer testable benchmarks.

major comments (2)

[§2] §2 (Definitions): the movement rules are invoked as 'various movement rules' without an explicit combinatorial model (synchronous/asynchronous token moves, collision rules, or time-indexed positions). This is load-bearing for the central claim that finite attainable maxima exist and are reached on paths, cycles, and topfull graphs.
[Characterization section] Characterization of topfull graphs: the claimed equivalence between 1-capacity equaling its theoretical maximum and the existence of certain factorizations or connectivity properties requires an explicit theorem showing that the modeling assumptions guarantee attainment; the abstract alone does not supply the derivation.

minor comments (2)

The abstract would be clearer if it briefly indicated which specific movement rules are used to obtain the stated values for paths and cycles.
Notation for d-capacity and 'topfull' should be introduced with a forward reference to the formal definition on first use.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful review and for highlighting areas where the presentation of our definitions and characterizations can be strengthened. We address each major comment below and will incorporate revisions to improve clarity and rigor.

read point-by-point responses

Referee: [§2] §2 (Definitions): the movement rules are invoked as 'various movement rules' without an explicit combinatorial model (synchronous/asynchronous token moves, collision rules, or time-indexed positions). This is load-bearing for the central claim that finite attainable maxima exist and are reached on paths, cycles, and topfull graphs.

Authors: We agree that an explicit combinatorial model is necessary to rigorously establish the finite attainable maxima. In the revised manuscript, we will expand §2 with a formal definition of the movement rules, including specifications for synchronous versus asynchronous updates, explicit collision-avoidance conditions, and time-indexed position sequences for each player. This will directly support the claims that the d-capacity is well-defined and attains finite maxima on the indicated graph families. revision: yes
Referee: [Characterization section] Characterization of topfull graphs: the claimed equivalence between 1-capacity equaling its theoretical maximum and the existence of certain factorizations or connectivity properties requires an explicit theorem showing that the modeling assumptions guarantee attainment; the abstract alone does not supply the derivation.

Authors: The manuscript already contains the full characterization and its proof in the dedicated section, connecting the attainment of the 1-capacity maximum to factorizations and connectivity. To address the concern directly, we will insert an explicit theorem statement that isolates the modeling assumptions and derives the equivalence from them, making the logical steps self-contained and independent of the abstract. revision: yes

Circularity Check

0 steps flagged

No significant circularity; results rest on independent combinatorial arguments

full rationale

The paper defines d-capacity directly from the traversal rules and then derives explicit values for paths and cycles via case analysis on vertex visits and distance constraints. Bounds for bipartite graphs and the topfull-graph characterization are obtained by linking to existing factorization and connectivity notions without reducing any claimed prediction or maximum back to a fitted parameter or self-citation that encodes the same quantity. No equation or definition is shown to be equivalent to its input by construction, and the movement-rule assumptions are stated as enabling conditions rather than derived from the final results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Ledger is inferred from abstract only; the paper relies on standard graph-theoretic background and introduces the d-capacity as a new quantity.

axioms (1)

standard math Standard definitions of paths, cycles, bipartite graphs, and graph factorizations from prior literature.
Invoked implicitly when stating results for these graph classes.

invented entities (1)

d-capacity no independent evidence
purpose: Quantifies maximum number of distance-d-separated simultaneous traversals visiting all vertices.
Newly defined in the paper; no independent evidence supplied in abstract.

pith-pipeline@v0.9.0 · 5620 in / 1210 out tokens · 30256 ms · 2026-05-19T20:46:30.713946+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Definition 3.2. … the direct d-capacity … maximum integer c such that there exists an ℓ-tour F … satisfying m_G(F)=d
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Lemma 3.19 … vertex disjoint cycle/edge cover … collision-free ℓ-march

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

Baniˇ c and A

I. Baniˇ c and A. Taranenko. Span of a graph: Keeping the safety distance. Discrete Math. Theor. Comput. Sci., 25(1), 2023

work page 2023
[2]

Dravec, M

T. Dravec, M. Mikalaˇ cki, and A. Taranenko. Graphs with span 1 and shortest optimal walks.Appl. Math. Comput., 500:129433, 2025

work page 2025
[3]

Erceg, A

G. Erceg, A. ˇSubaˇ si´ c, and T. Vojkovi´ c. Some results on the maximal safety distance in a graph.Filomat, 37(15):5123–5136, 2023

work page 2023
[4]

Graˇ siˇ c, C

M. Graˇ siˇ c, C. Mouron, and A. Taranenko. The strong vertex span of trees. Commun. Appl. Math. Comput., 8(3):1157–1170, 2026

work page 2026
[5]

Lov´ asz and M

L. Lov´ asz and M. D. Plummer.Matching Theory, volume 367 ofAMS Chelsea Publishing. American Mathematical Society, Providence, RI, 2009

work page 2009
[6]

Petersen

J. Petersen. Die theorie der regul¨ aren graphs.Acta Math., 15:193–220, 1891

work page
[7]

ˇSubaˇ si´ c and T

A. ˇSubaˇ si´ c and T. Vojkovi´ c. Vertex spans of multilayered cycle and path graphs.Axioms, 13(4):236, 2024

work page 2024
[8]

ˇSubaˇ si´ c and T

A. ˇSubaˇ si´ c and T. Vojkovi´ c. The relation between different edge spans of a graph.arXiv:2306.06714v2, 2025. submitted

work page arXiv 2025
[9]

W. T. Tutte. The 1-factors of oriented graphs.Proc. Amer. Math. Soc., 4(6):922–931, 1953

work page 1953
[10]

Prentice Hall, Upper Saddle River (N.J.), second edition, 2001

Douglas Brent West.Introduction to graph theory. Prentice Hall, Upper Saddle River (N.J.), second edition, 2001

work page 2001
[11]

H. Whitney. Congruent graphs and the connectivity of graphs.Amer. J. Math., 54(1):150–168, 1932

work page 1932
[12]

H. Whitney. Non-separable and planar graphs.Trans. Amer. Math. Soc., 34(2):339–362, 1932. 19

work page 1932

[1] [1]

Baniˇ c and A

I. Baniˇ c and A. Taranenko. Span of a graph: Keeping the safety distance. Discrete Math. Theor. Comput. Sci., 25(1), 2023

work page 2023

[2] [2]

Dravec, M

T. Dravec, M. Mikalaˇ cki, and A. Taranenko. Graphs with span 1 and shortest optimal walks.Appl. Math. Comput., 500:129433, 2025

work page 2025

[3] [3]

Erceg, A

G. Erceg, A. ˇSubaˇ si´ c, and T. Vojkovi´ c. Some results on the maximal safety distance in a graph.Filomat, 37(15):5123–5136, 2023

work page 2023

[4] [4]

Graˇ siˇ c, C

M. Graˇ siˇ c, C. Mouron, and A. Taranenko. The strong vertex span of trees. Commun. Appl. Math. Comput., 8(3):1157–1170, 2026

work page 2026

[5] [5]

Lov´ asz and M

L. Lov´ asz and M. D. Plummer.Matching Theory, volume 367 ofAMS Chelsea Publishing. American Mathematical Society, Providence, RI, 2009

work page 2009

[6] [6]

Petersen

J. Petersen. Die theorie der regul¨ aren graphs.Acta Math., 15:193–220, 1891

work page

[7] [7]

ˇSubaˇ si´ c and T

A. ˇSubaˇ si´ c and T. Vojkovi´ c. Vertex spans of multilayered cycle and path graphs.Axioms, 13(4):236, 2024

work page 2024

[8] [8]

ˇSubaˇ si´ c and T

A. ˇSubaˇ si´ c and T. Vojkovi´ c. The relation between different edge spans of a graph.arXiv:2306.06714v2, 2025. submitted

work page arXiv 2025

[9] [9]

W. T. Tutte. The 1-factors of oriented graphs.Proc. Amer. Math. Soc., 4(6):922–931, 1953

work page 1953

[10] [10]

Prentice Hall, Upper Saddle River (N.J.), second edition, 2001

Douglas Brent West.Introduction to graph theory. Prentice Hall, Upper Saddle River (N.J.), second edition, 2001

work page 2001

[11] [11]

H. Whitney. Congruent graphs and the connectivity of graphs.Amer. J. Math., 54(1):150–168, 1932

work page 1932

[12] [12]

H. Whitney. Non-separable and planar graphs.Trans. Amer. Math. Soc., 34(2):339–362, 1932. 19

work page 1932