Faculty of Science
http://hdl.handle.net/10294/147
2015-05-25T23:37:20ZOn the complexity of the positive semidefinite zero forcing number
http://hdl.handle.net/10294/5691
On the complexity of the positive semidefinite zero forcing number
Meagher, Karen; Fallat, Shaun; Yang, Boting
The positive semidefinite 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 forcing. We establish a relation between the zero forcing and the fastâ€“mixed searching, which implies some NP-completeness results for the zero forcing problem. Relationships between positive semidefinite zero forcing sets and clique coverings are well-understood for chordal graphs. Building upon constructions associated with optimal tree covers and forest covers, we present a linear time algorithm for computing the positive semidefinite zero forcing number of chordal graphs. We also prove that it is NP-complete to determine whether a graph has a positive semidefinite zero forcing set with an additional property.
2015-01-01T00:00:00ZParameter related ot the tree-width, zero forcing, and maximum nullity of a graph
http://hdl.handle.net/10294/5690
Parameter related ot the tree-width, zero forcing, and maximum nullity of a graph
Barioli, Francesco; Barrett, Wayne; Fallat, Shaun; Hall, Tracy; Hogben, Leslie; Shader, Bryan; van den Driessche, Pauline; van der Holst, Hein
Tree-width, and variants that restrict the allowable tree decompositions, play an important role
in the study of graph algorithms and have application to computer science. The zero forcing number is used
to study the maximum nullity/minimum rank of the family of symmetric matrices described by a graph. We
establish relationships between these parameters, including several Colin de Verdi`ere type parameters, and introduce
numerous variations, including the minor monotone floors and ceilings of some of these parameters. This leads to
new graph parameters and to new characterizations of existing graph parameters. In particular, tree-width, largeur
dâ€™arborescence, path-width, and proper path-width are each characterized in terms of a minor monotone floor of a
certain zero forcing parameter defined by a color change rule.
2013-01-01T00:00:00ZOn the relationship between zero forcing number and certain graph coverings
http://hdl.handle.net/10294/5689
On the relationship between zero forcing number and certain graph coverings
Alinaghipour, Fatemeh; Fallat, Shaun; Meagher, Karen
The zero forcing number and the positive zero forcing number of a graph are
two graph parameters that arise from two types of graph colourings. The zero
forcing number is an upper bound on the minimum number of induced paths in
the graph that cover all the vertices of the graph, while the positive zero forcing
number is an upper bound on the minimum number of induced trees in the
graph needed to cover all the vertices in the graph. We show that for a block-
cycle graph the zero forcing number equals the path cover number. We also
give a purely graph theoretical proof that the positive zero forcing number of
any outerplanar graphs equals the tree cover number of the graph. These ideas
are then extended to the setting of k-trees, where the relationship between the
positive zero forcing number and the tree cover number becomes more complex.
2014-01-01T00:00:00ZThe principal rank characteristic sequence over various fields
http://hdl.handle.net/10294/5688
The principal rank characteristic sequence over various fields
Barrett, Wayne; Butler, Steve; Catral, Minnie; Fallat, Shaun; Hall, Tracy; Hogben, Leslie; van den Driessche, Pauline; Young, Michael
Given an n-by-n matrix, its principal rank characteristic sequence is a sequence of
length n + 1 of 0s and 1s where, for k = 0; 1,..., n, a 1 in the kth position indicates
the existence of a principal submatrix of rank k and a 0 indicates the absence of such
a submatrix. The principal rank characteristic sequences for symmetric matrices over
various fields are investigated, with all such attainable sequences determined for all n
over any field with characteristic 2. A complete list of attainable sequences for real symmetric matrices of order 7 is reported.
2014-01-01T00:00:00Z