Cops, Robbers, and Algebraic Graphs

Imagine a robber moving through a finite network. A team of cops knows exactly where the robber is. Everyone can move only along edges, and the cops win as soon as one of them reaches the robber’s vertex.

How many cops are needed to guarantee capture?

The question sounds like a puzzle about pursuit. In graph theory, it becomes a surprisingly difficult problem about the global structure of networks.

For a connected graph $\Gamma$, its cop number $c(\Gamma)$ is the minimum number of cops that can guarantee capture, regardless of how the robber plays. A graph may contain millions of vertices, yet need only one or two cops. Other graphs force any winning strategy to use many more.

The central conjecture in the subject predicts that even the worst graphs cannot require too many.

If $\Gamma$ has $n$ vertices, Meyniel’s conjecture asserts that

$$c(\Gamma)=O(\sqrt n).$$

The conjecture remains open for general graphs.

There is even a much weaker question that is not known in full generality. The weak Meyniel conjecture asks only whether there exists some fixed $c>0$ such that every connected $n$-vertex graph satisfies

$$c(\Gamma)=O(n^{1-c}).$$

Instead of demanding the square-root scale, it asks merely for a power saving over the trivial linear scale.

This is the setting of a 2025 result by Arindam Biswas and Jyoti Prakash Saha. Rather than attack arbitrary graphs, they study networks whose vertices come from a finite group and whose edges are created by algebraic operations.

For these graphs, the robber’s motion is not merely a walk through a network. Every move carries algebraic information.

The paper’s central idea is to turn that information into a quantity that the cops can force to decrease.

The chase becomes a countdown.

---

The general problem: how difficult can pursuit become?

The game of cops and robbers is played on a finite connected graph.

First the cops choose their starting vertices. The robber then chooses a starting vertex after seeing the cops. The players subsequently alternate moves along edges, with the cops moving first. Capture occurs when a cop occupies the same vertex as the robber.

In the version used in the paper, the robber moves along an edge in every round. The authors note that allowing the robber to remain stationary changes their bounds by at most one additional cop.

The important point is that both sides have complete information. There is no uncertainty about the robber’s position.

The difficulty is strategic.

A single cop trying to catch a robber on a path has an obvious advantage: the robber eventually runs out of room. On a tree, the geometry still severely constrains escape. But a graph may contain many cycles, shortcuts and alternative routes. Progress toward the robber need not be permanent.

That makes the following question subtle:

Can we identify some measure of progress that the robber cannot undo?

For an arbitrary graph, there may be no natural answer.

One can measure graph distance, but distance can increase again. One can restrict parts of the graph, but another route may open elsewhere. Local movement does not automatically produce a monotone global quantity.

The situation changes when the graph itself is built from algebra.

---

From arbitrary graphs to algebraic graphs

Let $G$ be a finite group and let $S\subseteq G$.

The elements of $G$ will serve as vertices. The set $S$ specifies which moves are allowed.

The best-known construction is the Cayley graph.

Cayley graphs

The Cayley graph $C(G,S)$ has vertex set $G$, with an edge from $u$ to $v$ whenever

$$v=us$$

for some $s\in S$.

Thus moving through the graph means multiplying the current group element by one of the permitted elements of $S$.

If $S$ generates $G$, the graph is connected.

Cayley graphs have enormous symmetry. Multiplying every vertex by the same group element preserves the graph, so no vertex is intrinsically special.

This algebraic regularity has already proved useful in studying cops and robbers. In particular, important forms of Meyniel’s conjecture are known for some classes of Cayley graphs.

But Biswas and Saha are interested in graphs where this familiar symmetry is partly disrupted.

The first is obtained by inserting an inverse.

Cayley sum graphs

The Cayley sum graph $C_\Sigma(G,S)$ again has $G$ as its vertex set, but now $u$ and $v$ are related through

$$v=u^{-1}s, \qquad s\in S.$$

This looks like a small modification of a Cayley graph.

It is not.

Ordinary Cayley graphs are vertex-transitive: every vertex has exactly the same global position in the graph. Cayley sum graphs need not have this property.

The algebra remains, but one of its most useful geometric consequences disappears.

That makes Cayley sum graphs a natural test case:

Is the group structure itself enough to control pursuit, even when full vertex symmetry is lost?

Biswas and Saha show that it is.

Under suitable assumptions, the cop number is bounded directly in terms of the size of $S$.

For a connected, undirected Cayley sum graph with $S=S^{-1}$,

$$c\bigl(C_\Sigma(G,S)\bigr)\leq 2|S|.$$

To understand why, it is useful to forget the other graph families temporarily and follow this case in detail.

The proof contains the mechanism that drives almost everything else in the paper.

---

One model case: chasing a robber on a Cayley sum graph

Suppose from now on that

$$\Gamma=C_\Sigma(G,S)$$

is connected and undirected and that $S$ is symmetric:

$$S=S^{-1}.$$

The authors begin with $|S|$ primary cops.

Each primary cop is assigned a label $s\in S$.

So, instead of treating the cops as interchangeable tokens, the strategy gives every cop an algebraic direction.

The labels may change as the game proceeds, but they always remain inside $S$.

Why should labels help?

Because every move made by the robber also determines an element of $S$.

The strategy is designed to compare the robber’s current algebraic direction with the labels carried by the cops.

---

The gap between a cop and the robber

Suppose a cop occupies $z\in G$ and the robber occupies $y\in G$.

There is an algebraic expression describing their relative position.

Because a Cayley sum move involves inversion, the convenient expression alternates with the parity of the round. The authors define a gap $\Delta_{z,y}$ using either $z^{-1}y$ or $zy^{-1}$, according to the stage of the game.

The exact parity convention is needed for the proof, but the structural point is simpler:

Instead of measuring the ordinary graph distance from a cop to the robber, measure their relative position as an element of the group.

Once the gap is an element of $G$, the generating set $S$ allows us to factor it.

For a cop currently labelled $s$, write

$$\Delta_{z,y}=w\,s^{i},$$

where $w$ is chosen to be a shortest possible product of elements of $S$.

Suppose

$$w=g_{1}\,g_{2}\,\cdots\,g_{k}, \qquad g_{j}\in S.$$

The integer $k$ is called the tail of the cop.

The decomposition is

$$\Delta = \bigl(g_{1}\,g_{2}\,\cdots\,g_{k}\bigr)s^{i}.$$

Here $g_{1}\,g_{2}\,\cdots\,g_{k}$ is the arbitrary part, while $s^{i}$ is the structured part.

This seemingly technical definition is the central move of the proof.

The cops do not try immediately to reduce the entire gap to the identity.

They first try to eliminate the arbitrary part.

---

Why tail zero is special

Suppose the tail has reached zero.

Then

$$\Delta=s^{i}.$$

The relative position of the cop and robber is no longer an arbitrary group element. It belongs to the cyclic direction generated by a single element $s$.

A potentially complicated noncommutative pursuit problem has collapsed into the study of one exponent.

This creates a two-stage strategy:

$$\text{arbitrary gap} \longrightarrow s^{i} \longrightarrow e.$$

Or, in terms of complexity,

$$\text{reduce the tail first}, \qquad \text{then reduce the power}.$$

The difficult part is arranging cop moves so that this reduction is irreversible.

---

Every robber move has a connection

When the robber moves from $y$ to a new vertex $\widetilde y$, the edge relation guarantees that some element of $S$ is responsible.

The paper packages this element into what it calls the robber’s connection.

Its exact formula again depends on the parity of the round. In one parity it is essentially the generator used for the move; in the other, it appears after conjugation by the robber’s current position.

What matters is that

$$\xi_{y,\widetilde y}\in S.$$

So every round produces a distinguished element of the same set that labels the cops.

Now the strategy can compare two pieces of information:

• the label $s$ carried by a cop;
• the connection $\xi_{y,\widetilde y}$ produced by the robber’s move.

This comparison determines how that cop moves.

---

The key lemma: complexity never increases

The case analysis in the paper is detailed because the parity of the round, inversion and conjugation all have to be handled correctly.

But the purpose of those calculations can be summarized in one monotonicity statement.

For every primary cop:

1. its tail never increases;
2. when the robber’s connection is a power of the cop’s label and the tail is positive, the tail decreases by at least one;
3. once the tail is zero, certain robber moves reduce the remaining power by two.

This is the mechanism behind the theorem.

It is worth seeing the middle step explicitly.

Suppose the gap has the form

$$\Delta = g_{1}\,g_{2}\,\cdots\,g_{k}\,s^{i}, \qquad k>0,$$

and suppose the robber’s connection is a power of the cop’s label,

$$\xi=s^j.$$

The cop chooses its move specifically to cancel the first element $g_{1}$.

After the round, the new gap takes the form

$$\widetilde\Delta = g_{2}\,\cdots\,g_{k}\,s^{i+j}.$$

The exponent may have changed.

But that is not yet important.

The crucial event is

$$g_{1}\,g_{2}\,\cdots\,g_{k} \longrightarrow g_{2}\,\cdots\,g_{k}.$$

Hence

$$k\longrightarrow k-1.$$

One unit of arbitrary algebraic complexity has disappeared.

And the strategy guarantees that it cannot come back.

---

The proof is a potential argument

Viewed this way, the tail behaves like a potential function.

Many combinatorial arguments work by constructing a quantity

$$\Phi_0,\Phi_1,\Phi_2,\ldots$$

such that

$$\Phi_{r+1}\leq \Phi_r$$

on every step, with strict inequality sufficiently often.

Here the potential is not graph distance.

It is the length of the unwanted part of an algebraic factorization.

That distinction is essential.

The robber may move farther from a cop in ordinary geometric terms.

But the robber cannot restore a tail component that has already been eliminated.

The algebra remembers progress that graph distance would forget.

---

Why some cop must make progress

A monotone quantity is useful only if we know that it eventually decreases.

This is where the number $|S|$ enters.

There is one primary cop associated with each element of $S$.

Every robber move produces a connection belonging to $S$.

Therefore, over many rounds, the same relevant label must recur.

The pigeonhole principle forces repetition.

One cannot predict in advance which cop will become the successful one. But among the $|S|$ labels, some cop must repeatedly encounter the type of robber move that decreases its tail.

Since tails are nonnegative integers and never increase, enough such rounds eventually force

$$k=0$$

for one of the cops.

At that point,

$$\Delta=s^{i}.$$

The first phase of the pursuit is finished.

---

From a word to an exponent

Once the tail has vanished, only a power remains.

Suppose

$$\Delta=s^{i}.$$

The strategy is now arranged so that, when the robber’s connection is the inverse of the relevant label, the power changes as

$$i\longrightarrow i-2.$$

Repeated occurrences therefore give

$$i,\quad i-2,\quad i-4,\quad i-6,\ldots$$

There are two possible terminal cases.

Even power

If $i$ eventually reaches zero, then

$$\Delta=e.$$

The gap between the cop and robber is the identity.

They occupy the same vertex.

Capture is complete.

Odd power

But if the initial exponent has the opposite parity, repeated subtraction by two stops at

$$i=1.$$

The primary cop has almost caught the robber, but not quite.

This parity obstruction explains another feature of the proof.

The authors double the cops.

---

Why every primary cop gets a partner

For every primary cop $C$, introduce an auxiliary cop $C_{\mathrm{aux}}$. If the primary cop occupies a vertex $v$, its partner occupies $v^{-1}$.

Because of the assumptions imposed on the Cayley sum graph, the auxiliary cop can legally maintain this relationship as the primary cop moves.

The pair therefore tracks two algebraically related positions.

This is exactly what is needed when the exponent reaches one.

When

$$\Delta=s,$$

the next appropriate robber move places the robber not on the primary cop’s vertex but on the corresponding inverted position.

That is where the auxiliary cop is waiting.

So:

• exponent $0$ gives capture by the primary cop;
• exponent $1$ gives capture by the auxiliary cop.

The extra set of cops resolves the parity obstruction.

There are $|S|$ primary cops and $|S|$ auxiliary cops, giving

$$c\bigl(C_\Sigma(G,S)\bigr) \leq 2|S|.$$

The factor $2$ is therefore closely tied to the structure of this strategy. It is not simply inserted at the end of an estimate.

---

Why the assumptions cannot simply be ignored

The result is not stated for every pair $(G,S)$.

The hypotheses make the moves in the strategy legal.

For the Cayley sum graph theorem, the graph must be connected and undirected, and $S$ is assumed to be symmetric.

These requirements interact with the algebra.

For example, the labels of cops are conjugated during the strategy. If an element $s\in S$ is replaced by $g^{-1}sg$, the new label must still lie in $S$.

Similarly, inverses appear continually in the movement rules.

A symbolic cancellation in the group is useful only if it corresponds to an actual edge in the graph.

This is a recurring theme in algebraic combinatorics:

Algebra provides candidate moves; the hypotheses on the generating set determine whether those moves exist in the graph.

The assumptions are therefore part of the mechanism, not technical decoration.

---

The other algebraic graphs in the paper

The Cayley sum graph gives the cleanest place to see the argument.

The paper then considers two further constructions obtained by adding an automorphism

$$\sigma:G\to G.$$

The relevant automorphism satisfies

$$\sigma^2=\operatorname{id}.$$

So applying the twist twice restores the original group element.

This leads to two additional families.

---

Twisted Cayley graphs

In a twisted Cayley graph, a move from $x$ has the form

$$y=\sigma(xs), \qquad s\in S.$$

Compare this with the ordinary Cayley rule

$$y=xs.$$

After multiplying by a generator, we also apply the automorphism $\sigma$.

The paper considers the connected undirected case under additional assumptions, including symmetry of $S$ and closure of $S$ under conjugation.

Under these conditions,

$$c\bigl(C(G,S)^\sigma\bigr) \leq 2|S|.$$

---

Twisted Cayley sum graphs

Now combine both modifications: inversion and twisting.

A move is given by

$$y=\sigma(x^{-1}s).$$

This defines the twisted Cayley sum graph $C_\Sigma(G,S)^\sigma$. Again, under the hypotheses of the theorem—connectedness, undirectedness, symmetry of $S$, and an order-two automorphism—the authors obtain

$$c\bigl(C_\Sigma(G,S)^\sigma\bigr) \leq 2|S|.$$

At first sight, each new graph seems to require a new pursuit strategy.

In fact, the opposite happens.

The formulas change.

The proof architecture remains almost identical.

---

What survives when the graph is twisted?

For the Cayley sum graph, the central object was the factorization

$$\Delta=ws^{i}.$$

The same object remains useful in the twisted cases.

What has to change is the definition of $\Delta$.

The goal is to choose the gap so that, after both players move, the new gap can again be expressed in the same form and compared with the previous one.

For a twisted Cayley graph, the gap is defined using expressions such as $z^{-1}y$ on one parity of rounds and $\sigma(z^{-1}y)$

on the other.

For a twisted Cayley sum graph, the corresponding expressions combine $\sigma$ with the inversions already present in the untwisted sum graph.

These definitions can look artificial if read in isolation.

Their purpose becomes clearer if we ask the right question:

What definition makes the algebra after one complete round look like the algebra before the round?

Once the gap is chosen that way, the same tail decomposition becomes available:

$$\Delta=ws^{i}.$$

And the same three conclusions can be proved:

$$\text{tail never increases},$$

$$\text{appropriate robber move} \quad\Longrightarrow\quad k\mapsto k-1,$$

and, once $k=0$,

$$i\mapsto i-2.$$

That common lemma is the true reusable component of the paper.

---

The auxiliary cop changes with the graph

One more modification is needed.

The auxiliary cop must occupy the position that resolves the final parity obstruction. What that position should be depends on the graph’s edge rule.

For the ordinary Cayley sum graph, a primary cop at $v$ is paired with a cop at $v^{-1}$. For a twisted Cayley graph, the corresponding partner occupies $\sigma(v)$.

For a twisted Cayley sum graph, it occupies $\sigma(v^{-1})$. The formulas are different, but they express the same idea:

Apply to the primary cop’s position the involutive operation naturally built into the graph.

The auxiliary cop then shadows the primary cop under that operation.

When the power reduction stops at the odd endpoint, the robber lands on precisely that companion position.

Thus the proof adapts not by inventing a different strategy for each graph, but by modifying three interfaces:

1. the formula for the robber’s connection;
2. the formula for the cop–robber gap;
3. the transformation relating a primary cop to its auxiliary partner.

The invariant itself stays intact.

That is the conceptual reason the method extends.

---

Four graph families, one pursuit principle

The paper ultimately treats the following algebraic settings under their respective hypotheses:

$$\text{ordinary Cayley graphs},$$

$$\text{Cayley sum graphs},$$

$$\text{twisted Cayley graphs},$$

and

$$\text{twisted Cayley sum graphs}.$$

For the three latter classes, the new pursuit arguments give bounds of the form

$$c(\Gamma)\leq 2|S|.$$

For the relevant ordinary Cayley graphs, an earlier result of Frankl provides the corresponding ingredient.

The common theme is that the group structure gives the cops something an arbitrary graph does not naturally provide:

a coordinate system for relative position.

Once the cop–robber gap has been encoded algebraically, the pursuit problem becomes a problem about reducing a word.

---

But $2|S|$ is not yet a Meyniel bound

There is an obvious limitation.

Suppose the group has

$$|G|=n$$

elements.

Then the graph also has $n$ vertices.

If $|S|$ is small, the estimate

$$c(\Gamma)\leq2|S|$$

is excellent.

But what if $|S|$ is huge?

If, for example,

$$|S|\approx n,$$

then $2|S|$ is of order $n$, nowhere near Meyniel’s predicted $O(\sqrt n)$. So the local pursuit strategy alone is not enough.

The final part of the argument changes tactics completely.

Instead of asking how to chase the robber when there are few available moves, it exploits the fact that a graph with many algebraically generated edges is difficult for the robber to hide in at all.

---

Two regimes: sparse and dense

The authors split the problem according to the size of $S$.

This produces a particularly clean proof.

Regime 1: $S$ is small

Suppose

$$|S|<\sqrt n\log n.$$

The direct pursuit theorem gives

$$c(\Gamma) \leq 2|S| < 2\sqrt n\log n.$$

So sparse generating sets are handled by the tail-and-power strategy.

---

Regime 2: $S$ is large

Now suppose

$$|S|\geq\sqrt n\log n.$$

Trying to assign two cops per generator would be wasteful.

But a large $S$ makes the graph dense.

Here the authors use a covering theorem of Bollobás, Janson and Riordan.

In the required range, one can find a subset

$$T\subseteq G$$

with roughly square-root size such that

$$TS=G.$$

More precisely, the paper obtains a set with

$$|T|\leq 2\sqrt n$$

for the application at hand.

The equation

$$TS=G$$

means that every element of $G$ lies one $S$-move away from some suitable element of $T$, after making the appropriate translation for the graph family being considered.

Graph-theoretically, this produces a small dominating set.

A dominating set $D$ has the property that every vertex is either in $D$ or adjacent to a vertex in $D$.

Place a cop on every vertex of $D$.

The robber has nowhere to begin that is safely separated from all of them.

So in the dense regime one does not need the elaborate tail argument at all.

Density itself does the work.

---

Why the two arguments fit together

The proof therefore uses two opposite properties of $S$.

If $S$ is small, then $2|S|$ is small enough for the explicit pursuit strategy.

If $S$ is large, then the graph is sufficiently dense that a small dominating set exists.

The threshold

$$|S|\approx \sqrt n\log n$$

is where the two estimates meet.

This yields, for the classes covered by the theorem,

$$\boxed{ c(\Gamma)\leq 2\sqrt n\log n }$$

under the corresponding hypotheses.

The argument is a useful example of a general combinatorial technique:

When no single estimate is good across all parameter ranges, divide the objects into regimes where different mechanisms become effective.

Here those mechanisms could hardly be more different.

One is dynamic: chase the robber and decrease an invariant.

The other is static: occupy a dominating set before the chase develops.

---

What this says about Meyniel’s conjecture

Recall the original conjecture:

$$c(\Gamma)=O(\sqrt n).$$

The paper obtains

$$c(\Gamma)=O(\sqrt n\log n)$$

for the algebraic graph families under consideration.

So the logarithm has not disappeared.

The full Meyniel bound is therefore not obtained in these cases by this argument.

But the result is considerably stronger than the weak Meyniel conjecture.

For every fixed

$$c<\frac12,$$

we have

$$\sqrt n\log n = O(n^{1-c}).$$

Indeed,

$$\frac{\sqrt n\log n}{n^{1-c}} = \frac{\log n}{n^{1/2-c}} \longrightarrow 0$$

because $1/2-c>0$.

Thus

$$c(\Gamma)=O(n^{1-c})$$

for every fixed $c<1/2$.

The weak Meyniel conjecture therefore holds for these algebraic graph families.

More sharply, their cop numbers lie within a logarithmic factor of the bound predicted by Meyniel.

---

What the proof is really exploiting

It would be easy to summarize the paper as a sequence of estimates:

$$c(\Gamma)\leq2|S|$$

followed by

$$c(\Gamma)\leq2\sqrt n\log n.$$

But that misses the most interesting idea.

The central question is not simply how many cops to use.

It is how to make progress irreversible.

For a general graph, the obvious quantity—distance to the robber—is unreliable. A robber can often increase it on the next move.

The group structure provides a different notion of distance.

Write the relative position as

$$\Delta=ws^{i}.$$

Then separate two forms of complexity:

$$\underbrace{|w|}_{\text{tail}} \qquad\text{and}\qquad \underbrace{i}_{\text{power}}.$$

The strategy first removes the arbitrary part:

$$g_{1}\,g_{2}\,\cdots\,g_{k}\,s^{i} \longrightarrow g_{2}\,\cdots\,g_{k}\,s^{i'} \longrightarrow \cdots \longrightarrow s^j.$$

Then it removes the structured part:

$$s^j \longrightarrow s^{j-2} \longrightarrow s^{j-4} \longrightarrow \cdots.$$

The auxiliary cop handles the parity left over at the end.

So the intellectual progression of the proof is

$$\text{graph pursuit} \longrightarrow \text{group-valued gap} \longrightarrow \text{word decomposition} \longrightarrow \text{monotone tail} \longrightarrow \text{one exponent} \longrightarrow \text{capture}.$$

That is the main structural idea.

---

Where the method stops

The argument also makes clear what it does not prove.

First, the graph must belong to a structured algebraic class. Nothing in the proof produces a comparable tail invariant for an arbitrary graph.

Second, the hypotheses on $S$ and on the twisting automorphism matter. They ensure that conjugations, inversions and applications of $\sigma$ remain compatible with legal graph moves.

Third, the final estimate is $O(\sqrt n\log n)$,

not the conjectured $O(\sqrt n)$. The logarithm enters through the transition between the small-$S$ pursuit regime and the large-$S$ covering argument.

Removing it would require an additional idea, a sharper estimate, or a different way of combining algebraic pursuit with graph density.

The result therefore sits naturally between a solved special case and the full conjecture.

It shows that the algebra is powerful enough to obtain a substantial universal bound for these graph families, while leaving visible the gap that remains.

---

From pursuit to algebra and back

Cops and robbers begins as a geometric game.

A cop wants to get closer.

A robber wants to get farther away.

But on these graphs, ordinary geometry is not where the decisive progress occurs.

The useful quantity lives inside the group.

Every robber move produces a generator. Every cop carries one. Their relative position can be factored into an unwanted word and a controlled power. The strategy repeatedly deletes the unwanted word until only that power remains.

The graph tells the players where they may move.

The algebra tells the proof why the chase must eventually end.

And that is the broader lesson of the argument.

When a combinatorial object is built from algebra, the right way to measure progress need not look combinatorial at all.

Sources

• Arindam Biswas and Jyoti Prakash Saha, On the cop number and the weak Meyniel conjecture for algebraic graphs, European Journal of Combinatorics 128 (2025), Article 104168.

• Peter Frankl, On a pursuit game on Cayley graphs, Combinatorica 7 (1) (1987), 67-70.

• Peter Frankl, Cops and robbers in graphs with large girth and Cayley graphs, Discrete Applied Mathematics 17 (3) (1987), 301-305.

• Béla Bollobás, Svante Janson and Oliver Riordan, On covering by translates of a set, Random Structures & Algorithms 38 (1-2) (2011), 33-67.