Browsing by Author "Barrett, Wayne"

Filter results by typing the first few letters
Now showing 1 - 4 of 4
  • Thumbnail Image
    ItemOpen Access
    The maximum nullity of a complete edge subdivision graph is equal to it zero forcing number
    (International Linear Algebra Society, 2014-06) Barrett, Wayne; Butler, Steve; Catral, Minnie; Hall, Tracy; Fallat, Shaun; Hogben, Leslie; Young, Michael
    Barrett et al. asked in [W. Barrett et al. Minimum rank of edge subdivisions of graphs. Electronic Journal of Linear Algebra, 18:530–563, 2009.], whether the maximum nullity is equal to the zero forcing number for all complete subdivision graphs. We prove that this equality holds. Furthermore, we compute the value of M(F, °G) = Z(°G) by introducing the bridge tree of a connected graph. Since this equality is valid for all fields, °G has field independent minimum rank, and we also show that °G has a universally optimal matrix.
  • Thumbnail Image
    ItemOpen Access
    Note on Nordhaus-Gaddum problems for Colin de Verdiere type parameters
    (Public Knowledge Network, 2013) Barrett, Wayne; Fallat, Shaun; Hall, Tracy; Hogben, Leslie
    We establish the bounds 4 on the Nordhaus- Gaddum sum upper bound multipliers for all graphs G, in connections with certain Colin de Verdi ere type graph parameters. The Nordhaus-Gaddum sum lower bound is conjectured to be |G|-2, and if these parameters are replaced by the maximum nullity M(G), this bound is called the Graph Complement Conjecture in the study of minimum rank/maximum nullity problems.
  • Thumbnail Image
    ItemOpen Access
    Parameters Related to Tree-Width, Zero Forcing, and Maximum Nullity of a Graph
    (Wiley Periodicals, Inc., 2013) 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.
  • Thumbnail Image
    ItemOpen Access
    The principal rank characteristic sequence over various fields
    (Elsevier, 2014) 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.