9 citations · 42 across the 19 of their papers we have counts for
5 papers · 1 filter
Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
Édouard Bonnet, Julien Duron, John Sylvester +2
We show that for any natural number , there is a constant and a subgraph-closed class having, for any natural , at most graphs on vertices up to isomorphism, bu…
Cops and Robbers on Multi-Layer Graphs
Jessica Enright, Kitty Meeks, William Pettersson +1
We generalise the popular cops and robbers game to multi-layer graphs, where each cop and the robber are restricted to a single layer (or set of edges). We show that initial intuit…
Bounds on the Twin-Width of Product Graphs
William Pettersson, John Sylvester
Twin-width is a graph width parameter recently introduced by Bonnet, Kim, Thomassé & Watrigant. Given two graphs and and a graph product , we address the question: i…
Tangled Paths: A Random Graph Model from Mallows Permutations
Jessica Enright, Kitty Meeks, William Pettersson +1
We introduce the random graph which results from taking the union of two paths of length , where the vertices of one of the paths have been relabelled a…
Random walk hitting times and effective resistance in sparsely connected Erdős-Rényi random graphs
John Sylvester
We prove expectation and concentration results for the following random variables on an Erdős-Rényi random graph in the sparsely connected regime $\lo…