Span capacities of graphs
Mateja Grašič, Christopher Mouron, Aljoša Šubašić, Andrej Taranenko, Tanja Vojković · 2026
Read Span capacities of graphs by Mateja Grašič, Christopher Mouron, Aljoša Šubašić, Andrej Taranenko, Tanja Vojković (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-16852.txt.
Introduction
Grašič and colleagues introduce the d-capacity of a graph. It is the maximum number of players that can simultaneously traverse the graph, each visiting all vertices while keeping distance at least d under various movement rules. They determine capacities for paths and cycles and give bounds for bipartite graphs. They also characterize topfull graphs, where 1-capacities reach their theoretical maximum, linking them to graph factorizations and connectivity.
Catalog record
| CREATOR | Mateja Grašič, Christopher Mouron, Aljoša Šubašić, Andrej Taranenko, Tanja Vojković |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52996 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.16852
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Span capacities of graphs Mateja Grašič, Christopher Mouron, Aljoša Šubašić, Andrej Taranenko, Tanja Vojković Abstract The d d -capacity of a graph G G is introduced as the maximum number of players that can simultaneously traverse G G such that each player visits all vertices while maintaining a distance of at least d 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. Keywords: span, span capacity, topfull graphs, factorizations, 2-connectivity. MSC2020 : 05C12, 05C70, 05C75. 1 Introduction and motivation In 2023, Banič and Taranenko [ 1 ] introduced a graph-theoretic analogue of a well-known topological concept, the span of a continuum. Their work was motivated by the need for maintaining safe interpersonal distances during movement, particularly relevant during the pandemic. In the graph-theoretic setting, they considered two players, Alice and Bob, moving on the vertices of a graph via its edges, each with the aim of visiting all vertices or all edges, giving rise to the notions of vertex spans and edge spans. Three types of movement rules usually used in games on graphs were studied: • Traditional movement rules: the players may, independently, either move or stay in place at each step; • Active movement rules: both players must move at each step; • Lazy movement rules: at each step, exactly one of the players moves. For each of the two spans, these movement rules yield three variants, namely the strong, direct, and Cartesian span, respectively. The terminology is motivated by the characterizations of each span using graph products of the same name. These were also the basis for a polynomial time algorithm for determining the corresponding span for any connected graph. Graphs with the vertex span for each variant equal to zero were also characterised. Since then, several aspects of graph spans have been investigated in subsequent papers. In [ 3 ] , vertex spans of several graph classes were determined and some relations between vertex spans were presented, i.e. the strong vertex span of any graph is always greater than or equal to the maximum of the values of the direct and Cartesian span, while the direct and Cartesian span differ by at most one, for any observed graph. It was shown in [ 2 ] that the vertex and edge span of the same variant can differ by at most 1. Structural properties of graphs with the strong vertex span equal to 1 and an exponential time algorithm for the computation of shortest optimal walks with respect to the strong vertex span were also presented. In [ 4 ] using the novel notion of switching walks and triods of a tree the strong vertex span of any tree was determined and a linear time algorithm for its computation was presented. This vastly improved the time complexity of the general algorithm presented in [ 1 ] . Spans for specific graph classes, including multilayered cycles and paths were studied in [ 7 ] . It was shown that vertex span values depend solely on the length of cycles and paths, instead the number of layers. Edge spans were studied in [ 8 ] , and a family of graphs was found for which strong edge span is greater than both direct and Cartesian span. A family with such a property is yet to be found for vertex spans, if it exists, which indicates vertex and edge spans may differ in some important behaviours. All previous papers consider only two players traversing a graph, which naturally leads to the generalization of the concept of span to settings with more than two players. This raises the following question: given that all players moving in a graph must maintain a prescribed distance d , what is the maximum number of players that can be placed on a graph? We introduce this number as the d -capacity of a graph . This question is also motivated by practical scenarios in which it is important, for safety or other reasons, to determine how many individuals can move through a given space or venue while maintaining a prescribed distance. In analogy with the three movement rules used in the definition of graph spans, we define the strong, direct, and Cartesian d -capacity. The paper is organized as follows. In Section 2 , we establish a necessary theoretical framework and introduce the terminology of marches and tours. Section 3 contains our main results. We first define the three variants of span capacities and investigate their values for paths and cycles. We then provide bounds for bipartite graphs and conclude with a structural characterization of topfull graphs, linking the maximum 1 -capacity of a graph to its connectivity and factorization properties. We conclude the paper with some open problems. 2 Theory of marches First, we provide some initial definitions. All graphs considered in this paper are finite, connected, simple, and undirected. For any graph theoretic notions not explicitly defined here, see [ 10 ] . Let G be a connected graph. Let \ell be a non-negative integer. A weak walk W on G is a sequence of vertices w_{0},w_{1},\ldots,w_{\ell} in V(G) such that w_{i}w_{i+1}\in E(G) or w_{i}=w_{i+1} for all i\in\{0,1,\ldots,\ell-1\} . We denote it by W:w_{0},\ldots,w_{\ell} and also call it a weak \ell -walk. Note that if w_{i}w_{i+1}\in E(G) for every i\in\{0,1,\ldots,\ell-1\} , then this is the common notion of a walk in G . Thus, every walk is also a weak walk. Note, \ell may be 0, hence a (weak) 0 -walk is just one vertex. Moreover, since we consider (weak) walks parametrized by time, we may refer to indices of the walks as to points in time . For this reason we also call a function f:\{0,1,\ldots,\ell\}\rightarrow V(G) with f(i)f(i+1)\in E(G) , for any i\in\{0,1,\ldots,\ell-1\} , a walk. Similarly, we call a function f:\{0,1,\ldots,\ell\}\rightarrow V(G) with f(i)=f(i+1) or f(i)f(i+1)\in E(G) , for any i\in\{0,1,\ldots,\ell-1\} , a weak walk. Definition 2.1 . Let G be a connected graph, \ell a non-negative integer and f,g:\{0,...,\ell\}\rightarrow V(G) functions. The distance between f and g is defined as m_{G}(f,g)=\min\{d_{G}(f(i),g(i))\mid i\in\{0,...,\ell\}\}. Definition 2.2 . Let G be a connected graph, p\geq 2 a natural number and \ell a non-negative integer. Let f_{1},f_{2},\ldots,f_{p}:\{0,\ldots,\ell\}\rightarrow V(G) be functions. The distance between f_{1},f_{2},\ldots,f_{p} is m_{G}(f_{1},f_{2},\ldots,f_{p})=\min\{m_{G}(f_{i},f_{j})\mid i,j\in\{1,2,\ldots,p\}\text{ and }i\not=j\}. Definition 2.3 . Let G be a connected graph, p a natural number and \ell a non-negative integer. We say that F=\{f_{1},\ldots,f_{p}\} is a (weak) \ell -march on G if each f_{i}:\{0,1,\ldots,\ell\}\rightarrow V(G) is a (weak) walk on G . Also, we define F(i):=\{f_{1}(i),\ldots,f_{p}(i)\} to be the i -th stage of F . We call \ell the length of F . Remark 2.4 . When we say that F=\{f_{1},\ldots,f_{p}\} is a (weak) march on G , this means that there exists a non-negative integer \ell such that F is a (weak) \ell -march on G . For a (weak) march F=\{f_{1},\ldots,f_{p}\} on some connected graph G , we define m_{G}(F):=m_{G}(f_{1},f_{2},\ldots,f_{p}). Also, if p=1 define m_{G}(F):=\infty . Definition 2.5 . Let G be a connected graph, and F=\{f_{1},\ldots,f_{p}\} a (weak) march on G . We