Faculty of Science
http://hdl.handle.net/10294/147
20160528T22:32:02Z

The enhanced principal rank characteristic sequence for skewsymmetric matrices
http://hdl.handle.net/10294/6588
The enhanced principal rank characteristic sequence for skewsymmetric matrices
Fallat, Shaun; Olesky, Dale; van den Driessche, Pauline
The enhanced principal rank characteristic sequence (eprsequence) was originally defined for an n ×n real symmetric matrix or an n ×n Hermitian matrix. Such a sequence is defined to be l1l2···ln where lk is A,S, or N depending on whether all, some, or none of the matrix principal minors of order k are nonzero. Here we give a complete characterization of the attainable eprsequences for real skewsymmetric matrices. With the constraint that lk=0 if k is odd, we show that nearly all eprsequences are attainable by skewsymmetric matrices, which is in contrast to the case of real symmetric or Hermitian matrices for which many eprsequences are forbidden.
©2015
20150815T00:00:00Z

On 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 nontraditional 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 NPcompleteness results for the zero forcing problem. Relationships between positive semidefinite zero forcing sets and clique coverings are wellunderstood 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 NPcomplete to determine whether a graph has a positive semidefinite zero forcing set with an additional property.
20150101T00:00:00Z

Parameters Related to TreeWidth, Zero Forcing, and Maximum Nullity of a Graph
http://hdl.handle.net/10294/5690
Parameters Related to TreeWidth, 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
Treewidth, 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, treewidth, largeur
d’arborescence, pathwidth, and proper pathwidth are each characterized in terms of a minor monotone floor of a
certain zero forcing parameter defined by a color change rule.
20130101T00:00:00Z

On 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 ktrees, where the relationship between the
positive zero forcing number and the tree cover number becomes more complex.
20140101T00:00:00Z