Show simple item record

dc.contributor.advisor Hicks, Illya V
dc.creatorDavila, Randy R
dc.date.accessioned 2016-01-07T17:28:35Z
dc.date.available 2016-01-07T17:28:35Z
dc.date.created 2015-05
dc.date.issued 2015-04-16
dc.date.submitted May 2015
dc.identifier.citation Davila, Randy R. "Bounding the Forcing Number of a Graph." (2015) Master’s Thesis, Rice University. https://hdl.handle.net/1911/87761.
dc.identifier.urihttps://hdl.handle.net/1911/87761
dc.description.abstract The forcing number, denoted F(G), is an upper bound for the maximum nullity of all symmetric matrices with a sparsity pattern described by the simple graph G. Simple lower and upper bounds are δ ≤ F(G) where δ is the minimum degree and F (G) ≤ n − 1 where n is the order of the graph. This thesis provides improvements on the minimum degree lower bound in the case that G has girth of at least 5. In particular, it is shown that 2δ − 2 ≤ F (G) for graphs with girth of at least 5; this can be further improved when G has a small cut set. Further, this thesis also conjectures a lower bound on F(G) as a function of the girth, g, and δ.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectZero Forcing Number
k-Forcing Number
dc.title Bounding the Forcing Number of a Graph
dc.type Thesis
dc.contributor.committeeMember Tapia, Richard A
dc.contributor.committeeMember Zhang, Yin
dc.date.updated 2016-01-07T17:28:36Z
dc.type.material Text
thesis.degree.department Computational and Applied Mathematics
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Masters
thesis.degree.name Master of Arts


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record