Publications (10)
On the Complexity of the Positive Semidefinite Zero Forcing Number
Shaun Fallat, Karen Meagher, Boting Yang
The positive zero forcing number of a graph is a graph parameter that arises from a non-traditional type of graph colouring, and is related to a more conventional version of zero f…
The Cop Number of the One-Cop-Moves Game on Planar Graphs
Ziyuan Gao, Boting Yang
Cops and robbers is a vertex-pursuit game played on graphs. In the classical cops-and-robbers game, a set of cops and a robber occupy the vertices of the graph and move alternately…
Approximation Algorithms for Preference Aggregation Using CP-Nets
Abu Mohammmad Hammad Ali, Boting Yang, Sandra Zilles
This paper studies the design and analysis of approximation algorithms for aggregating preferences over combinatorial domains, represented using Conditional Preference Networks (CP…
Ovoids of Generalized Quadrangles of Order and Delsarte Cocliques in Related Strongly Regular Graphs
Mohammad Adm, Ryan Bergen, Ferdinand Ihringer +4
We investigate strongly regular graphs for which Hoffman's ratio bound and CvetcoviÄ's inertia bound are equal. This means that , where is the number of v…
Achievable multiplicity partitions in the inverse eigenvalue problem of a graph
Mohammad Adm, Shaun Fallat, Karen Meagher +3
Associated to a graph is a set of all real-valued symmetric matrices whose off-diagonal entries are nonzero precisely when the corresponding vertices of the gr…
Compressed Cliques Graphs, Clique Coverings and Positive Zero Forcing
Shaun Fallat, Karen Meagher, Abolghasem Soltani +1
Zero forcing parameters, associated with graphs, have been studied for over a decade, and have gained popularity as the number of related applications grows. In particular, it is w…
Algorithms for Cut Problems on Trees
Iyad Kanj, Guohui Lin, Tian Liu +7
We study the {\sc multicut on trees} and the {\sc generalized multiway Cut on trees} problems. For the {\sc multicut on trees} problem, we present a parameterized algorithm that ru…
Infection in Hypergraphs
Ryan Bergen, Shaun Fallat, Adam Gorr +5
In this paper a new parameter for hypergraphs called hypergraph infection is defined. This concept generalizes zero forcing in graphs to hypergraphs. The exact value of the infecti…
Deduction, Constrained Zero Forcing, and Constrained Searching
Andrea Burgess, Danny Dyer, Kerry Ojakian +3
Deduction is a recently introduced graph searching process in which searchers clear the vertex set of a graph with one move each, with each searcher's movement determined by which…
Properties of a -analogue of zero forcing
Steve Butler, Craig Erickson, Shaun Fallat +6
Zero forcing is a combinatorial game played on a graph where the goal is to start with all vertices unfilled and to change them to filled at minimal cost. In the original variation…