Tom Johnston

most citedGame Connectivity and Adaptive Dynamics

2 citations · 2 across the 1 of their papers we have counts for

collaborators

Showing math.COShow all

7 papers · 1 filter

math.CO2025

A note on inverting the dijoin of oriented graphs

Natalie Behague, Tom Johnston, Natasha Morrison +1

For an oriented graph $D$ and a set $X \subseteq V (D)$ , the inversion of $X$ in $D$ is the graph obtained from $D$ by reversing the orientation of each edge that has both endpoints…

math.CO2025

Short reachability networks

Carla Groenland, Tom Johnston, Jamie Radcliffe +1

We investigate the following generalisation of permutation networks. We say a sequence $T = (T_{1}, \dots, T_{ℓ})$ of transpositions in $S_{n}$ forms a $t$ -reachability network if, for ev…

math.CO2025

Infinite induced-saturated graphs

Marthe Bonamy, Carla Groenland, Tom Johnston +2

A graph $G$ is $H$ -induced-saturated if $G$ is $H$ -free but deleting any edge or adding any edge creates an induced copy of $H$ . There are non-trivial graphs $H$ , such as $P_{4}$ , fo…

math.CO2025

Shotgun assembly of random graphs

Tom Johnston, Gal Kronenberg, Alexander Roberts +1

In the graph shotgun assembly problem, we are given the balls of radius $r$ around each vertex of a graph and asked to reconstruct the graph. We study the shotgun assembly of the E…

math.CO2024

Counting graphic sequences via integrated random walks

Paul Balister, Serte Donderwinkel, Carla Groenland +2

Given an integer $n$ , let $G (n)$ be the number of integer sequences $n - 1 \geq d_{1} \geq d_{2} \geq \dots \geq d_{n} \geq 0$ that are the degree sequence of some graph. We show that $G(n)=(c+o(1))…

math.CO2024

A Polynomial Upper Bound for Poset Saturation

Paul Bastide, Carla Groenland, Maria-Romina Ivan +1

Given a finite poset $P$ , we say that a family $F$ of subsets of $[n]$ is $P$ -saturated if $F$ does not contain an induced copy of $P$ ,…