Exploring Word-Representable Temporal Graphs

Duncan Adamson

REVIEW 4 major objections 4 minor 23 references

Exploring Word-Representable Temporal Graphs

T0 review · 4 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A word-representable temporal graph can be explored in at most 2dn timesteps, and this is asymptotically optimal.

desk verdict New model, flawed proof: the paper's central 2dn exploration bound rests on Lemma 7, which is false on the paper's own path construction. read the letter →

arxiv 2502.07496 v1 pith:XE27YMHN submitted 2025-02-11 cs.DS

Duncan Adamson This is my paper · ORCID

classification cs.DS MSC 05C8568R1005C12

keywords temporalgraphsword-representablegraphexplorationalternatingwordsdiameterlowerbounds

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper introduces word-representable temporal graphs, where a single word over the vertex alphabet is cut into contiguous factors, each factor is a timestep, and an edge is active at that timestep whenever either endpoint appears in the factor. The paper studies how fast a single agent can visit every vertex by moving along edges that are active in successive timesteps. It presents two upper bounds: when the underlying graph is connected and has diameter d, graphs whose representing word is at least n(2dn+d) symbols long are explorable in at most 2dn timesteps; and when every timestep is itself connected, exploration takes at most 2δn timesteps, where δ is the minimum degree. It also constructs, for every n and d, a word-representable temporal graph with n vertices and diameter d that needs Ω(dn) timesteps, which would make the 2dn bound asymptotically optimal. The general upper bound rests on a structural lemma about how close the k-th occurrences of distance-d vertices must lie in the word.

What carries the argument

The central object is the word representation itself: a word w over the vertex alphabet is parcelled into timestep factors, each containing no repeated symbol, and an edge between two vertices is present in a timestep if and only if one of its endpoints occurs in that factor. The argument's engine is the occurrence-proximity lemma (Lemma 7), which asserts that for any two vertices at graph distance d, the index of the i-th occurrence of one vertex differs from that of the other by at most d. From this lemma the paper derives the bounded-dormancy corollary that no edge can be inactive for more than d consecutive timesteps, which in turn justifies the waiting-time analysis of the exploration walk.

What would settle it

Check Lemma 7 on the paper's own path construction for n=4, whose word is 1 2 1 3 2 4 3 4: vertices 1 and 4 are at distance 3 in the underlying path, yet the first occurrence of 1 is at position 1 and the first occurrence of 4 is at position 6, so the position difference (5) exceeds d=3. If this single check confirms the violation, the lemma is false and the general upper-bound argument is unsupported.

Watch

Extended reading notes

Core claim

The central discovery is that word-representable temporal graphs have a built-in bounded-dormancy property: once an edge appears in a timestep, it must reappear within a fixed window of consecutive timesteps. The proof of the main upper bound, Theorem 11, uses a spanning tree of the underlying graph and traverses it edge by edge, waiting at each vertex until the next tree edge becomes active; the bounded-dormancy property caps each wait at d timesteps, giving 2dn in total. For always-connected graphs, a stronger dormancy bound in terms of the minimum degree δ gives the 2δn upper bound. The lower-bound construction layers many copies of a slow path gadget, forcing an agent to advance through at most five layers and then wait Ω(d) timesteps, which sums to Ω(dn).

Load-bearing premise

The load-bearing premise is Lemma 7, which says that in the representing word, the k-th occurrence of any two vertices at graph distance d lie at most d positions apart; if that proximity bound fails, the proof that no edge stays inactive for more than d consecutive timesteps—and hence the 2dn upper bound—collapses.

Editorial extensions

If this is right

If Theorem 11 holds, then every sufficiently long word-representable temporal graph with connected underlying graph is explorable in time linear in the product of diameter and vertex count, and no asymptotic improvement is possible because of Theorem 22.
The always-connected bound of 2δn is stronger than the diameter bound when the graph is dense, because δ can be much smaller than d; this gives a faster schedule for graphs that are well-connected at every step.
The lower-bound construction shows that temporal graphs can encode forced waiting periods, so any exploration algorithm for this representation class must budget for Ω(dn) timesteps in the worst case.
For path-like word-representable temporal graphs, the paper's construction yields a quadratic lower bound (Ω(n^2) for diameter d=Θ(n)), indicating that even very sparse graph classes can be slow to explore.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The occurrence-proximity lemma (Lemma 7) can be tested directly on the paper's own path construction: for n=4, w = 1 2 1 3 2 4 3 4, vertices 1 and 4 are distance 3 apart, yet their first occurrence positions are 1 and 6, which violates the lemma's bound; if this counterexample stands, the general upper-bound proof loses its foundation, though the always-connected bound (which relies on a different
The lower-bound construction suggests a natural stress test for the constants: computing the exact optimal exploration time for the constructed path graphs would reveal whether the factor 2 in 2dn can be reduced, since the construction's waiting gaps indicate the true worst case may have a smaller constant.
The definition of word-representable temporal graphs ties the timing of edges to the internal repetition structure of a single word; this could be exploited to give simple exploration algorithms for specific word families (e.g., periodic words), and to characterise which temporal graphs admit such a compact representation.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper introduces word-representable temporal graphs, a new model that is a natural synthesis of word-representable graph theory and temporal graph exploration. The definitions are clean, the examples are helpful, and the idea of bounding exploration time via occurrence positions in the representing word is genuinely interesting. The always-connected section (2δn bound) is a plausible extension of known spanning-tree-with-waiting techniques, though Lemma 3's proof has a real gap: edge activity only requires one endpoint to appear in the factor, not both, so the propagation argument is not justified as written.

The general upper bound, however, is not just missing a detail—it rests on a false lemma. Lemma 7 claims that if Dist(vx, vy) = d, the i-th occurrence positions of x and y differ by at most d. The paper's own n=4 path construction gives w = 12132434, where vertices 1 and 4 are at distance 3, but their first occurrences are at positions 1 and 6, and 6 > 1+3. So Lemma 7 is simply false, and no missing constant saves it. Lemma 9 explicitly uses Lemma 7 to derive the waiting-time bound, and Corollary 10 and Theorem 11 depend on Lemma 9. That means the main 2dn upper bound is unproven in this manuscript. The lower-bound section is also sketchy: Theorem 17's summation has a missing parenthesis and the argument is informal, and Theorem 22 is too terse to verify the claimed Ω(dn) bound for all d in [1, n].

The paper is not written in bad faith; it is a genuine attempt at a new model, and the proof errors are internal logical gaps rather than circular reasoning or overclaiming of prior work. The citation pattern is appropriate and the related work is relevant. But the central theorem is currently unsupported.

Who gets value from this? Someone working on temporal graph exploration or word-representable graphs might find the model worth thinking about, and the false lemma is instructive as a caution about mixing occurrence positions and graph distances. I would not cite the 2dn result in its current form. However, the model itself and the always-connected question may be salvageable, so I would send this to a serious referee rather than desk-reject—ideally with the expectation of major revision and a corrected or weakened main theorem.

Referee Report

4 major / 4 minor

Summary. The paper introduces word-representable temporal graphs by partitioning a word representing a graph into factors with no repeated symbols, and declares an edge active in a timestep if at least one of its endpoints appears in the corresponding factor. The main claimed results are: (i) every always-connected word-representable temporal graph can be explored in 2δn timesteps, where δ is the minimum degree of the underlying graph (Theorem 4); (ii) if the representing word has length at least n(2dn+d) and the underlying graph has diameter d, the graph can be explored in 2dn timesteps (Theorem 11); and (iii) a lower-bound construction requiring Ω(dn) timesteps, which would make the bound asymptotically tight (Theorem 22). The paper is self-contained and proposes a genuinely new temporal graph model, but the central proofs contain serious gaps, including a false lemma on occurrence positions.

Significance. If the results were correct, the paper would contribute a new class of temporal graphs with a compact word representation and tight single-agent exploration bounds, complementing the existing literature on always-connected temporal graphs. The model is cleanly defined and the lower-bound construction is an interesting attempt to match the upper bound. However, the main theorems are not established by the arguments given: the always-connected result rests on an invalid inference in Lemma 3, and the general upper bound rests on Lemma 7, which is false on the paper's own path example. Because these are load-bearing errors in the central claims, the current manuscript cannot be accepted or recommended for minor revision.

major comments (4)

[Section 3, Lemma 3 and Theorem 4] The proof of Lemma 3 incorrectly strengthens the consequence of Corollary 2. Corollary 2 only says that the edge (vx,vy) is active in at least one timestep in a window of length min(d(vx),d(vy))+1. By the definition of Et in Section 2, an edge is active when the factor contains at least one of its endpoints, so the union of the factor alphabets over the window is only guaranteed to contain x or y, not necessarily both. The proof nevertheless states 'Therefore, x,y ∈ alph(w[St,...])', which is exactly the simultaneous-occurrence property needed to propagate degree bounds through neighbours. Since Theorem 4's waiting argument uses Lemma 3 to bound the delay at every vertex by δ, the always-connected 2δn upper bound is not established as written.
[Section 4, Lemma 7] Lemma 7 is false. The path construction of Section 4.1 with n=4 gives w=12132434, whose represented graph has edges (1,2), (2,3), and (3,4), so Dist(1,4)=3. The first occurrence of 1 is at position 1 and the first occurrence of 4 is at position 6, but the lemma requires γ_1 ≤ χ_1 + d = 4. The second occurrences are at positions 3 and 8, again violating γ_2 ≤ χ_2 + d = 6. Thus the claimed relation between occurrence indices of vertices at distance d is not merely unproved; it fails on the paper's own construction. Since Lemma 9 explicitly invokes Lemma 7 and Corollary 10 and Theorem 11 inherit that dependence, the general 2dn upper bound is unsupported.
[Section 4, Lemma 9] Independently of the falsity of Lemma 7, the proof of Lemma 9 contains an unjustified step: after assuming that the edge (vx,vy) is absent for d consecutive timesteps, it asserts that 'there must exist some symbol z such that |π{z}(w[St,St+d+1−1])| = d'. No argument is given that a single symbol must appear in each of those timestep factors, and the definition of timestep factors does not force consecutive factor alphabets to intersect. Consequently, even replacing Lemma 7 by a correct statement would not make the proof of Lemma 9 complete as written.
[Section 4.1, Theorem 22 construction] The lower-bound construction is incompletely specified: in the definition of the word v, the factors u2 and u3 are written as 'u2 = 0(1,2)(2,2)...' and 'u3 = 0(...)', where 0 is not a vertex symbol of the alphabet Σ = {(i,j)}. The paper's model in Section 2 defines words over the vertex alphabet only, so a separator symbol outside the alphabet is not admitted, and treating 0 as an ordinary letter would change the active-edge condition. The construction therefore needs a formal definition of the intended alphabet and the role of this symbol before Theorem 22 can be verified.

minor comments (4)

[Section 4, Lemma 6] The statement of Lemma 6 contains a self-referential typo: it compares |π{x}(w)| with itself instead of comparing |π{x}(w)| with |π{y}(w)|. The proof has a similar garbled inequality, though the intended triangle-inequality argument for the number of occurrences is clear.
[Section 4.1, Theorem 17] Theorem 17 states that the constructed word has length 4n^2, but the construction uses w^n where w has length 2n, giving length 2n^2. In the proof, sums such as Σ_{i∈[1,n/3]} ⌊2n−5⌋/4−3 are missing parentheses around the summand, making the displayed algebra ambiguous.
[Section 4.1, Observation 12] The displayed formula in Observation 12 conditions on the parity of k, the repetition count, where the intended condition appears to be the parity of the local index ℓ; as printed the formula is difficult to parse and should be rewritten.
[Throughout] There are numerous notation and typesetting errors, for example '(vx,vy) /∈ T′t' in Lemma 9 should presumably be '(vx,vy) ∉ Et′', and the bibliography contains the placeholder venue 'CVIT 2016'. These need correction in any revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is self-contained; the main proof gaps are internal logical errors, not reductions to the paper's own inputs.

full rationale

The paper does not fit parameters to data and then rename them as predictions, nor does it define its central objects in terms of the results it claims. The word-representable temporal graph model is defined directly from a word via start points and alternating occurrences, and the exploration bounds are derived from lemmas about occurrence positions and timestep structure. No external benchmark or fitted value is used. The citations in the related work section, including the author's own prior work [1], are contextual and are not load-bearing for the new theorems. The proof of Theorem 11 relies on Lemma 7, and Lemma 7 is in fact false on the paper's own path construction; however, that is a mathematical error in the internal argument, not a circular step. A false lemma does not make the derivation circular unless the lemma's content is assumed in the statement being proved, which is not the case here. Similarly, the lower bound construction in Section 4.1 is independent of the upper bound and does not presuppose the claimed optimality. Therefore, there is no identifiable circularity of any of the enumerated kinds, and the appropriate score is 0.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

No fitted parameters are present. The central claims rest on structural lemmas about word-representable graphs; two of these lemmas (Lemma 3 and Lemma 7) are not proven correctly, and Lemma 7 is false, so the ledger records them as unsupported premises.

assumptions (2)

ad hoc to paper Lemma 7: occurrence indices of vertices at graph distance d differ by at most d.
This lemma is false, as shown by the paper's own path construction for n=4, but it is required for Lemma 9 and Theorem 11.
ad hoc to paper Lemma 3: every edge appears in every δ+1 consecutive timesteps in an always connected word-representable temporal graph.
The proof is invalid because edge activity only implies at least one endpoint appears in a factor, not both endpoints. The lemma remains unproven.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Exploring Word-Representable Temporal Graphs." pith.science (2026). https://pith.science/paper/XE27YMHN

@misc{pith2026250207496,
  author       = {Pith},
  title        = {Pith review of: Exploring Word-Representable Temporal Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XE27YMHN}},
  note         = {Machine review of arXiv:2502.07496}
}

abstract

Word-representable graphs are a subset of graphs that may be represented by a word $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$. 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 \emph{exploration}, asking for the fastest schedule such that a given agent may explore all $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\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(2dn + d)$, with a connected underlying graph, the full graph can be explored in $2 d n$ timesteps, where $d$ is the diameter of the graph. We show this is asymptotically optimal by providing a class of graphs of diameter $d$ requiring $\Omega(d n)$ timesteps to explore, for any $d \in [1, n]$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 19 canonical work pages

[1]

Faster exploration of some temporal graphs

Duncan Adamson, Vladimir V Gusev, Dmitriy Malyshev, and Viktor Zamaraev. Faster exploration of some temporal graphs. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022) . Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2022

work page 2022
[2]

Kernelizing temporal exploration problems

Emmanuel Arrighi, Fedor V Fomin, Petr Golovach, and Petra Wolf. Kernelizing temporal exploration problems. arXiv preprint arXiv:2302.10110 , 2023

arXiv 2023
[3]

New results on word-representable graphs

Andrew Collins, Sergey Kitaev, and Vadim V Lozin. New results on word-representable graphs. Discrete Applied Mathematics , 216:136--141, 2017

work page 2017
[4]

Circle graphs and monadic second-order logic

Bruno Courcelle. Circle graphs and monadic second-order logic. Journal of Applied Logic , 6(3):416--442, 2008. URL: https://www.sciencedirect.com/science/article/pii/S1570868307000316, https://doi.org/10.1016/j.jal.2007.05.001 doi:10.1016/j.jal.2007.05.001

work page doi:10.1016/j.jal.2007.05.001 2008
[5]

Optimizing reachability sets in temporal graphs by delaying

Argyrios Deligkas and Igor Potapov. Optimizing reachability sets in temporal graphs by delaying. Inf. Comput. , 285(Part):104890, 2022

work page 2022
[6]

Exploiting automorphisms of temporal graphs for fast exploration and rendezvous

Konstantinos Dogeas, Thomas Erlebach, Frank Kammer, Johannes Meintrup, and William K Moses Jr. Exploiting automorphisms of temporal graphs for fast exploration and rendezvous. arXiv preprint arXiv:2312.07140 , 2023

arXiv 2023
[7]

Deleting edges to restrict the size of an epidemic in temporal networks

Jessica Enright, Kitty Meeks, George B Mertzios, and Viktor Zamaraev. Deleting edges to restrict the size of an epidemic in temporal networks. Journal of Computer and System Sciences , 119:60--77, 2021

work page 2021
[8]

On temporal graph exploration

Thomas Erlebach, Michael Hoffmann, and Michael Kammer. On temporal graph exploration. Journal of Computer and System Sciences , 119:1--18, 2021

work page 2021

Show all 23 references

[9]

Two moves per time step make a difference

Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, and Jakob T Spooner. Two moves per time step make a difference. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019

2019
[10]

Thomas Erlebach and Jakob T. Spooner. Exploration of k -edge-deficient temporal graphs. In Anna Lubiw and Mohammad Salavatipour, editors, Algorithms and Data Structures , pages 371--384, Cham, 2021. Springer International Publishing

2021
[11]

Parameterised temporal exploration problems

Thomas Erlebach and Jakob T Spooner. Parameterised temporal exploration problems. Journal of Computer and System Sciences , 135:73--88, 2023

2023
[12]

Generalized word-representable graphs

Zhidan Feng, Henning Fernau, Pamela Fleischmann, Kevin Mann, and Silas Cato Sacher. Generalized word-representable graphs. arXiv preprint arXiv:2411.03274 , 2024

2024 arXiv
[13]

Word-representable graphs from a word's perspective

Pamela Fleischmann, Lukas Haschke, Tim L \"o ck, and Dirk Nowotka. Word-representable graphs from a word's perspective. Acta Informatica , 61(4):383--400, 2024. https://doi.org/10.1007/s00236-024-00462-y doi:10.1007/s00236-024-00462-y

2024 doi
[14]

Enumeration and extensions of word-representants

Marisa Gaetz and Caleb Ji. Enumeration and extensions of word-representants. Discrete Applied Mathematics , 284:423--433, 2020

2020
[15]

On the representation number of a crown graph

Marc Glen, Sergey Kitaev, and Artem Pyatkin. On the representation number of a crown graph. Discrete Applied Mathematics , 244:89--93, 2018

2018
[16]

Alternation graphs

Magn \'u s M Halld \'o rsson, Sergey Kitaev, and Artem Pyatkin. Alternation graphs. In Graph-Theoretic Concepts in Computer Science: 37th International Workshop, WG 2011, Tepl \'a Monastery, Czech Republic, June 21-24, 2011. Revised Papers 37 , pages 191--202. Springer, 2011

2011
[17]

Halldórsson, Sergey Kitaev, and Artem Pyatkin

Magnús M. Halldórsson, Sergey Kitaev, and Artem Pyatkin. Semi-transitive orientations and word-representable graphs. Discrete Applied Mathematics , 201:164--171, 2016. URL: https://www.sciencedirect.com/science/article/pii/S0166218X15003868, https://doi.org/10.1016/j.dam.2015....

2016 doi
[18]

A comprehensive introduction to the theory of word-representable graphs

Sergey Kitaev. A comprehensive introduction to the theory of word-representable graphs. In International Conference on Developments in Language Theory , pages 36--67. Springer, 2017

2017
[19]

Words and graphs

Sergey Kitaev and Vadim Lozin. Words and graphs . Springer, 2015

2015
[20]

On representable graphs

Sergey Kitaev and Artem Pyatkin. On representable graphs. Journal of Automata, Languages and Combinatorics , 13(1):45--54, 2008. https://doi.org/10.25596/jalc-2008-045 doi:10.25596/jalc-2008-045

2008 doi
[21]

Reducing reachability in temporal graphs: Towards a more realistic model of real-world spreading processes

Kitty Meeks. Reducing reachability in temporal graphs: Towards a more realistic model of real-world spreading processes. In Conference on Computability in Europe , pages 186--195. Springer, 2022

2022
[22]

Traveling salesman problems in temporal graphs

Othon Michail and Paul G Spirakis. Traveling salesman problems in temporal graphs. Theoretical Computer Science , 634:1--23, 2016

2016
[23]

Minimum length word-representants of word-representable graphs

Eshwar Srinivasan and Ramesh Hariharasubramanian. Minimum length word-representants of word-representable graphs. Discrete Applied Mathematics , 343:149--158, 2024

2024

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.

[1] [1]

Faster exploration of some temporal graphs

Duncan Adamson, Vladimir V Gusev, Dmitriy Malyshev, and Viktor Zamaraev. Faster exploration of some temporal graphs. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022) . Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2022

work page 2022

[2] [2]

Kernelizing temporal exploration problems

Emmanuel Arrighi, Fedor V Fomin, Petr Golovach, and Petra Wolf. Kernelizing temporal exploration problems. arXiv preprint arXiv:2302.10110 , 2023

arXiv 2023

[3] [3]

New results on word-representable graphs

Andrew Collins, Sergey Kitaev, and Vadim V Lozin. New results on word-representable graphs. Discrete Applied Mathematics , 216:136--141, 2017

work page 2017

[4] [4]

Circle graphs and monadic second-order logic

Bruno Courcelle. Circle graphs and monadic second-order logic. Journal of Applied Logic , 6(3):416--442, 2008. URL: https://www.sciencedirect.com/science/article/pii/S1570868307000316, https://doi.org/10.1016/j.jal.2007.05.001 doi:10.1016/j.jal.2007.05.001

work page doi:10.1016/j.jal.2007.05.001 2008

[5] [5]

Optimizing reachability sets in temporal graphs by delaying

Argyrios Deligkas and Igor Potapov. Optimizing reachability sets in temporal graphs by delaying. Inf. Comput. , 285(Part):104890, 2022

work page 2022

[6] [6]

Exploiting automorphisms of temporal graphs for fast exploration and rendezvous

Konstantinos Dogeas, Thomas Erlebach, Frank Kammer, Johannes Meintrup, and William K Moses Jr. Exploiting automorphisms of temporal graphs for fast exploration and rendezvous. arXiv preprint arXiv:2312.07140 , 2023

arXiv 2023

[7] [7]

Deleting edges to restrict the size of an epidemic in temporal networks

Jessica Enright, Kitty Meeks, George B Mertzios, and Viktor Zamaraev. Deleting edges to restrict the size of an epidemic in temporal networks. Journal of Computer and System Sciences , 119:60--77, 2021

work page 2021

[8] [8]

On temporal graph exploration

Thomas Erlebach, Michael Hoffmann, and Michael Kammer. On temporal graph exploration. Journal of Computer and System Sciences , 119:1--18, 2021

work page 2021