• Login
    View Item 
    •   oURspace Home
    • Faculty of Science
    • Department of Mathematics & Statistics
    • Mathematics & Statistics Faculty
    • Shaun Fallat
    • View Item
    •   oURspace Home
    • Faculty of Science
    • Department of Mathematics & Statistics
    • Mathematics & Statistics Faculty
    • Shaun Fallat
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Parameters Related to Tree-Width, Zero Forcing, and Maximum Nullity of a Graph

    Thumbnail
    View/Open
    jgt21637_Rev_EV.pdf (2.194Mb)
    Date
    2013
    Author
    Barioli, Francesco
    Barrett, Wayne
    Fallat, Shaun
    Hall, Tracy
    Hogben, Leslie
    Shader, Bryan
    van den Driessche, Pauline
    van der Holst, Hein
    Metadata
    Show full item record
    URI
    http://hdl.handle.net/10294/5690
    Abstract
    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.
    Collections
    • Shaun Fallat

    Copyright © 2020 University of Regina
    Contact Us | Send Feedback | Archer Library | University of Regina

     

     

    Browse

    All of oURspaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    About

    About oURspacePoliciesLicensesContacts

    Statistics

    View Usage Statistics

    Copyright © 2020 University of Regina
    Contact Us | Send Feedback | Archer Library | University of Regina