G. MacGillivray

activity

20162026

most citedCharacterizations and algorithms for generalized Cops and Robbers games

8 citations · 20 across the 17 of their papers we have counts for

collaborators

19 papers

math.CO2026

The complexity of frugal digraph homomorphisms

Stefan Bard, Gary MacGillivray, Jacobus Swarts

For an integer $t \geq 1$ , a homomorphism of a digraph G to a digraph $H$ is $t$ -frugal if no more than $t$ in-neighbours of any vertex of $G$ have the same image. There is a dicho…

math.CO2023

Boundary and Hearing Independent Broadcasts in Graphs and Trees

Jules Hoepner, Gary MacGillivray, Kieka Mynhardt

A broadcast on a connected graph G with vertex set V(G) is a function $f : V (G) \to {0, 1, ..., diam (G)}$ such that $f (v) \leq e (v)$ (the eccentricity of $v$ ) for all…

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

Fractional eternal domination: securely distributing resources across a network

Fnu Devvrit, Aaron Krim-Yee, Nithish Kumar +4

This paper initiates the study of fractional eternal domination in graphs, a natural relaxation of the well-studied eternal domination problem. We study the connections to flows an…

cs.DM2022

Homomorphically Full Oriented Graphs

Thomas Bellitto, Christopher Duffy, Gary MacGillivray

Homomorphically full graphs are those for which every homomorphic image is isomorphic to a subgraph. We extend the definition of homomorphically full to oriented graphs in two diff…

math.CO2022★ 1 cited

Switching $m$ -edge-coloured graphs using non-Abelian groups

Chris Duffy, Gary MacGillivray, Ben Tremblay

Let $G$ be a graph whose edges are each assigned one of the $m$ -colours $1, 2, \dots, m$ , and let $Γ$ be a subgroup of $S_{m}$ . The operation of switching at a vertex $x$ with respe…

math.CO2022

Complexity of injective homomorphisms to small tournaments, and of injective oriented colourings

Russell J. Campbell, Nancy E. Clarke, Gary MacGillivray

Several possible definitions of local injectivity for a homomorphism of an oriented graph $G$ to an oriented graph $H$ are considered. In each case, we determine the complexity of…

math.CO2022

Obstructions to some injective oriented colourings

Russell Campbell, Nancy E. Clarke, Gary MacGillivray

Each of several possible definitions of local injectivity for a homomorphism of an oriented graph $G$ to an oriented graph $H$ leads to an injective oriented colouring problem. For…

math.CO2022★ 1 cited

The 2-colouring problem for $(m, n)$ -mixed graphs with switching is polynomial

Richard C Brewster, Arnott Kidner, Gary MacGillivray

A mixed graph is a set of vertices together with an edge set and an arc set. An $(m, n)$ -mixed graph $G$ is a mixed graph whose edges are each assigned one of $m$ colours, and whose…

math.CO2021

Eternal Domination in Trees

William F. Klostermeyer, Gary MacGillivray

Mobile guards on the vertices of a graph are used to defend the graph against an infinite sequence of attacks on vertices. A guard must move from a neighboring vertex to an attacke…

math.CO2021★ 1 cited

Switching $(m, n)$ -mixed graphs with respect to Abelian groups

E. Leclerc, G. MacGillivray, J. M. Warren

We extend results of Brewster and Graves for switching $m$ -edge coloured graphs with respect to a cyclic group to switching $(m, n)$ -mixed graphs with respect to an Abelian group.…

math.CO2021

Eternal Domination and Clique Covering

Gary MacGillivray, C. M. Mynhardt, Virgélot Virgile

We study the relationship between the eternal domination number of a graph and its clique covering number using both large-scale computation and analytic methods. In doing so, we a…

math.CO2021

Proving exact values for the $2$ -limited broadcast domination number on grid graphs

Aaron Slobodin, Gary MacGillivray, Wendy Myrvold

We establish exact values for the $2$ -limited broadcast domination number of various grid graphs, in particular $C_{m} □ C_{n}$ for $3 \leq m \leq 6$ and all $n \geq m$ , $P_m \squa…

math.CO2021★ 3 cited

2-limited broadcast domination on grid graphs

Aaron Slobodin, Gary MacGillivray, Wendy Myrvold

We establish upper and lower bounds for the 2-limited broadcast domination number of various grid graphs, in particular the Cartesian product of two paths, a path and a cycle, and…

math.SP2019

Inertias of Laplacian matrices of weighted signed graphs

Keivan Hassani Monfared, Gary MacGillivray, Dale D. Olesky +1

We study the sets of inertias achieved by Laplacian matrices of weighted signed graphs. First we characterize signed graphs with a unique Laplacian inertia. Then we show that there…

cs.DM2018

Oriented Colourings of Graphs with Maximum Degree Three and Four

Christopher Duffy, Gary MacGillivray, Eric Sopena

We show that any orientation of a graph with maximum degree three has an oriented 9-colouring, and that any orientation of a graph with maximum degree four has an oriented 69-colou…

cs.DM2017★ 4 cited

Complexity of locally-injective homomorphisms to tournaments

Stefan Bard, Thomas Bellitto, Christopher Duffy +2

For oriented graphs $G$ and $H$ , a homomorphism $f : G \to H$ is locally-injective if, for every $v \in V (G)$ , it is injective when restricted to some combination of the in-…

math.CO2017★ 8 cited

Characterizations and algorithms for generalized Cops and Robbers games

Anthony Bonato, Gary MacGillivray

We propose a definition of generalized Cops and Robbers games where there are two players, the Pursuer and the Evader, who each move via prescribed rules. If the Pursuer can ensure…

cs.DM2016★ 2 cited

Hitting minors, subdivisions, and immersions in tournaments

Jean-Florent Raymond

The Erdős-Pósa property relates parameters of covering and packing of combinatorial structures and has been mostly studied in the setting of undirected graphs. In this note, we use…

The complexity of frugal digraph homomorphisms

Boundary and Hearing Independent Broadcasts in Graphs and Trees

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

Fractional eternal domination: securely distributing resources across a network

Homomorphically Full Oriented Graphs

Switching m-edge-coloured graphs using non-Abelian groups

Complexity of injective homomorphisms to small tournaments, and of injective oriented colourings

Obstructions to some injective oriented colourings

The 2-colouring problem for (m,n)-mixed graphs with switching is polynomial

Eternal Domination in Trees

Switching (m,n)-mixed graphs with respect to Abelian groups

Eternal Domination and Clique Covering

Proving exact values for the 2-limited broadcast domination number on grid graphs

2-limited broadcast domination on grid graphs

Inertias of Laplacian matrices of weighted signed graphs

Oriented Colourings of Graphs with Maximum Degree Three and Four

Complexity of locally-injective homomorphisms to tournaments

Characterizations and algorithms for generalized Cops and Robbers games

Hitting minors, subdivisions, and immersions in tournaments

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

Switching $m$ -edge-coloured graphs using non-Abelian groups

The 2-colouring problem for $(m, n)$ -mixed graphs with switching is polynomial

Switching $(m, n)$ -mixed graphs with respect to Abelian groups

Proving exact values for the $2$ -limited broadcast domination number on grid graphs