Mathematics & Statistics Faculty

Permanent URI for this communityhttps://hdl.handle.net/10294/4260

Browse

Browsing Mathematics & Statistics Faculty by Subject "clique cover number"

Filter results by typing the first few letters
Now showing 1 - 2 of 2
  • Thumbnail Image
    ItemOpen Access
    On the complexity of the positive semidefinite zero forcing number
    (Elsevier, 2015) 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.
  • Thumbnail Image
    ItemOpen Access
    On the relationship between zero forcing number and certain graph coverings
    (2014) 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.