10.33531/ETD/34
Grout, Jason
Jason
Grout
Brigham Young University - Provo
Ultraconnected and Critical Graphs
Brigham Young University - Provo
2004
Dissertation
Graph theory.
Graphic methods.
Matrices.
2003-11-14
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.