Department of Mathematics & Statistics
http://hdl.handle.net/10294/339
2017-05-27T23:23:37Z
2017-05-27T23:23:37Z
The enhanced principal rank characteristic sequence for skew-symmetric matrices
Fallat, Shaun
Olesky, Dale
van den Driessche, Pauline
http://hdl.handle.net/10294/6588
2016-01-29T07:00:19Z
2015-08-15T00:00:00Z
The enhanced principal rank characteristic sequence for skew-symmetric matrices
Fallat, Shaun; Olesky, Dale; van den Driessche, Pauline
The enhanced principal rank characteristic sequence (epr-sequence) 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 epr-sequences for real skew-symmetric matrices. With the constraint that lk=0 if k is odd, we show that nearly all epr-sequences are attainable by skew-symmetric matrices, which is in contrast to the case of real symmetric or Hermitian matrices for which many epr-sequences are forbidden.
©2015
2015-08-15T00:00:00Z
On the complexity of the positive semidefinite zero forcing number
Meagher, Karen
Fallat, Shaun
Yang, Boting
http://hdl.handle.net/10294/5691
2015-05-13T07:00:25Z
2015-01-01T00:00:00Z
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:00Z
Parameters Related to 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
http://hdl.handle.net/10294/5690
2015-12-10T07:00:16Z
2013-01-01T00:00:00Z
Parameters Related to 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:00Z
On the relationship between zero forcing number and certain graph coverings
Alinaghipour, Fatemeh
Fallat, Shaun
Meagher, Karen
http://hdl.handle.net/10294/5689
2015-05-13T07:00:22Z
2014-01-01T00:00:00Z
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:00Z