Exploring Word-Representable Temporal Graphs
Duncan Adamson · 2025
Read Exploring Word-Representable Temporal Graphs by Duncan Adamson (2025) 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-2502-07496.txt.
Introduction
Duncan Adamson extends a word-based way of describing graphs to graphs that change over time, in a research paper from 2025. In the static version, a word lists vertices, and two vertices are linked when their letters alternate in the word. Adamson slices the word into steps, so the graph can shift from step to step.
He then asks how fast an agent can visit every vertex in such a moving graph. If the graph stays connected at each step, he bounds the tour length by the smallest vertex degree and the vertex count. For general cases, the bound uses the graph's diameter instead. Matching examples show these bounds are close to the best possible.
Catalog record
| CREATOR | Duncan Adamson |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-07496
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Exploring Word-Representable Temporal Graphs Duncan Adamson Abstract Word-representable graphs are a subset of graphs that may be represented by a word w w over an alphabet composed of the vertices in the graph. In such graphs, an edge exists if and only if the occurrences of the corresponding vertices alternate in the word w w . We generalise this notion to temporal graphs, constructing timesteps by partitioning the word into factors (contiguous subwords) such that no factor contains more than one copy of any given symbol. With this definition, we study the problem of exploration , asking for the fastest schedule such that a given agent may explore all n n vertices of the graph. We show that if the corresponding temporal graph is connected in every timestep, we may explore the graph in 2 δ n 2\delta n timesteps, where δ \delta is the lowest degree of any vertex in the graph. In general, we show that, for any temporal graph represented by a word of length at least n ( 2 d n + d ) n(2dn+d) , with a connected underlying graph, the full graph can be explored in 2 d n 2dn timesteps, where d d is the diameter of the graph. We show this is asymptotically optimal by providing a class of graphs of diameter d d requiring Ω ( d n ) \Omega(dn) timesteps to explore, for any d ∈ [ 1 , n ] d\in[1,n] . School of Computer Science, University of St Andrews, United [email protected]://orcid.org/0000-0003-3343-2435 ccs \textcolor redReplace ccsdesc macro with valid one keywords Temporal Graphs, Word-Representable Graphs † † runningauthor: D. Adamson † † copyright: Duncan Adamson † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Word-Representable graphs, first introduced by Kitaev and Pyatkin [ 20 ] , are a subset of graphs that may be represented in a concise manner via a word (or string) of symbols. In these graph, the vertices are represented by the alphabet, while edges are defined by the structure of the word. See [ 18 ] and [ 19 ] for an overview of the main results on word-representable graphs. Much work on word-representable graphs has focused on determining which such graphs are representable [ 3 , 12 , 14 , 15 , 16 , 23 ] . Such work has shown that a large number of graph classes are representable by word graphs, including three colourable graphs, circle graphs, and crown graphs. As such, the study of problems on these graphs are non-trivial. In this work, we extend the notion of word-representable graphs to temporal graphs . Temporal graphs are a generalisation of static graphs, replacing the single edge set with an ordered sequence of sets. Each edge set is used to define a timestep (also known as a snapshot), during which the only active edges are those in the corresponding timestep. Temporal graphs have attracted a large amount of attention in recent years, with a particular focus on reachability [ 5 , 7 , 21 ] and exploration [ 1 , 2 , 6 , 8 , 9 , 10 , 11 , 22 ] . Our Contributions We present a set of results on the problem of exploring word-representable temporal graphs. This combines research on word-representable graphs, temporal graphs, and graph exploration. We provide two primary results. First, we show that for any word-representable temporal graph where each timestep is a fully connected graph, we can construct an exploration schedule requiring at most 2\delta n timesteps, where \delta is the minimum degree of any vertex in the graph and n the number of vertices. Second, we show that for any word-representable temporal graph where the underlying graph is connected and the word representation requires at least n(2dn+d) symbols, we can construct an exploration schedule requiring 2dn timesteps, where d is the diameter of the graph, and n the number of vertices. Finally, we show that, for any number of vertices n and diameter d , there exists a word-representable temporal graph with n vertices and diameter d requiring \Omega(dn) timesteps to explore. Related Work While there is a large body of work on both word-representable graphs and exploration of temporal graphs, we highlight a small number of papers in both fields of particular relevance. Regarding word-representable graphs, we point first to the work of Kitaev and Pyatkin [ 20 ] who introduced word-representable graphs as a tool for semigroup theory. From the prespective of structural results on word-representable graphs, in [ 4 ] , Courcelle shows that circle graphs are word-representable. Halldorson et al. [ 17 ] strengthen this by showing that comparability graphs and all 3 -colourable graphs a word-representable, as well as presenting communication from Limouzy that cover graphs are word-representable. On the negative side, Halldorson et al. show that it is NP-hard to determine if a given triangle free graph is word-representable. Regarding the exploration of temporal graphs, we first mention the landmark paper by Erlebach et al. [ 8 ] , which established many of the key ideas behind temporal graph exploration. In particular, they show a general O(n^{2}) upper bound on the length of the fastest exploration schedule for a single agent on an always connected temporal graph. This is complemented by schedules of length O(n^{1.5}k^{1.5}\log n) for graphs with treewidth k , O(n^{1.8}\log n) for planar graphs, O(n) for cycles with one chord, and O(n\log^{3}n) for 2\times n grids. Building on this, Erlebach and Spooner showed in [ 10 ] that an always connected temporal graph in which each timestep is at most k -edges inactive can be explored in O(kn\log n) timesteps. Adamson et al. [ 1 ] further showed that k -chord graphs can be explored in O(kn) timesteps, that graphs with treewidth k can be explored in O(kn^{1.5}\log n) timesteps, and that planar graphs can be explored in O(n^{1.75}\log n) timesteps. 2 Preliminaries Let \mathcal{N}=\{1,2,\ldots\} denote the natural numbers and set \mathcal{N}_{0}=\mathcal{N}\cup\{0\} . Let [i,n]=\{i,i+1,\ldots,n\} for all i,n\in\mathcal{N}_{0} with i\leq n . Graphs and Temporal Graphs We define a graph G by a tuple containing a set V of vertices, and set E\subseteq V\times V of edges, each a pair of vertices. In this paper, we consider only undirected graphs , by which we assume that (v_{i},v_{j})=(v_{j},v_{i}) . When writing an edge explicitly as (v_{i},v_{j}) we call v_{i} the start point and v_{j} the end point of the edge. Given an arbitrary edge e and vertex v , we use v\in e to indicate that v is one of the vertices in e . We call two vertices v_{i},v_{j}\in V neighbours if (v_{i},v_{j})\in E . We denote by N(v) the set of neighbours of v , formally, N(v)=\{v^{\prime}\in V\mid(v,v^{\prime})\in E\} . The degree of a vertex v\in V , denoted d(v) , is equal to the number of neighbours of v , formally d(v)=|N(v)| . A