Ultraconnected and Critical Graphs

<p>We investigate the ultraconnectivity condition on graphs, and provide further connections between critical and ultraconnected graphs in the positive definite partial matrix completion problem. We completely characterize when the join of graphs is ultraconnected, and prove that ultraconnectivity is preserved by Cartesian products. We completely characterize when adding a vertex to an ultraconnected graph preserves ultraconnectivity. We also derive bounds on the number of vertices which guarantee ultraconnectivity of certain classes of regular graphs. We give results from our exhaustive enumeration of ultraconnected graphs up to 11 vertices. Using techniques involving the Lovász theta parameter for graphs, we prove certain classes of graphs are critical (and hence ultraconnected) in the positive definite partial matrix completion problem.</p>

Name thesis:degree_name

MS

Grantor dc:publisher

Brigham Young University - Provo

Author dc:creator

• Grout, Jason Nicholas

• ultraconnected
• critical
• partial matrix
• positive definite
• graph
• Lovász theta parameter
• completion
• matrix
• Mathematics

Language dc:language

English

Repository record dc:identifier

https://scholarsarchive.byu.edu/etd/34

OAI identifier oai:identifier

oai:scholarsarchive.byu.edu:etd-1033