R. Brewster

activity

20172024

most citedGraph Homomorphism Reconfiguration and Frozen

H

-Colourings

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

collaborators

Showing math.COShow all

5 papers · 1 filter

math.CO2024

Broadcast independence and packing in certain classes of trees

Richard C. Brewster, Kiara A. McDonald

Given a graph $G = (V, E)$ of diameter $d$ , a broadcast is a function $f : V (G) \to {0, 1, \dots, d}$ where $f (v)$ is at most the eccentricity of $v$ . A vertex $v$ is broadcasting i…

math.CO2023

A dichotomy theorem for $Γ$ -switchable $H$ -colouring on $m$ -edge coloured graphs

Richard Brewster, Arnott Kidner, Gary MacGillivray

Let $G$ be a graph in which each edge is assigned one of the colours $1, 2, \dots, m$ , and let $Γ$ be a subgroup of $S_{m}$ . The operation of switching at a vertex $x$ of $G$ with r…

math.CO2023

The Realizability of Theta Graphs as Reconfiguration Graphs of Minimum Independent Dominating Sets

Richard Brewster, Kieka Mynhardt, Laura Teshima

The independent domination number $i (G)$ of a graph $G$ is the minimum cardinality of a maximal independent set of $G$ , also called an $i (G)$ -set. The $i$ -graph of $G$ is the graph…

math.CO2018

Broadcast domination and multipacking: bounds and the integrality gap

Laurent Beaudou, Richard C. Brewster, Florent Foucaud

The dual concepts of coverings and packings are well studied in graph theory. Coverings of graphs with balls of radius one and packings of vertices with pairwise distances at least…

math.CO2017★ 4 cited

Graph Homomorphism Reconfiguration and Frozen $H$ -Colourings

Richard C. Brewster, Jae-Baek Lee, Benjamin Moore +2

For a fixed graph $H$ , the reconfiguration problem for $H$ -colourings (i.e. homomorphisms to $H$ ) asks: given a graph $G$ and two $H$ -colourings $φ$ and $ψ$ of $G$ , does there exis…

Broadcast independence and packing in certain classes of trees

A dichotomy theorem for Γ-switchable H-colouring on m-edge coloured graphs

The Realizability of Theta Graphs as Reconfiguration Graphs of Minimum Independent Dominating Sets

Broadcast domination and multipacking: bounds and the integrality gap

Graph Homomorphism Reconfiguration and Frozen H-Colourings

A dichotomy theorem for $Γ$ -switchable $H$ -colouring on $m$ -edge coloured graphs

Graph Homomorphism Reconfiguration and Frozen $H$ -Colourings