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.
","abstract_html":"<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>","abstract_has_math":false,"creators":["Grout, Jason Nicholas"],"institution":"Brigham Young University - Provo","degree_name":"MS","degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-07-24T01:27:16Z","subjects":["ultraconnected","critical","partial matrix","positive definite","graph","Lovász theta parameter","completion","matrix","Mathematics"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://scholarsarchive.byu.edu/etd/34","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Grout, Jason Nicholas"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2004-05-05T07:00:00Z"]},{"key":"dc:publisher","label":"Institution","values":["Brigham Young University - Provo"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["ultraconnected","critical","partial matrix","positive definite","graph","Lovász theta parameter","completion","matrix","Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://scholarsarchive.byu.edu/etd/34","https://scholarsarchive.byu.edu/context/etd/article/1033/viewcontent/ETD_CISOPTR_133.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Physical and Mathematical Sciences; Mathematics"]},{"key":"dc:description.abstract","label":"Abstract","values":["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.
"]},{"key":"dc:format","label":"Dc Format","values":["application:pdf"]},{"key":"dc:source","label":"Dc Source","values":["Brigham Young University - Provo"]},{"key":"dc:title","label":"Title","values":["Ultraconnected and Critical Graphs"]}]}],"canonical_facts":{"dc:creator":["Grout, Jason Nicholas"],"dc:date":["2004-05-05T07:00:00Z"],"dc:description":["Physical and Mathematical Sciences; Mathematics"],"dc:description.abstract":["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.
"],"dc:format":["application:pdf"],"dc:identifier":["https://scholarsarchive.byu.edu/etd/34","https://scholarsarchive.byu.edu/context/etd/article/1033/viewcontent/ETD_CISOPTR_133.pdf"],"dc:language":["English"],"dc:publisher":["Brigham Young University - Provo"],"dc:source":["Brigham Young University - Provo"],"dc:subject":["ultraconnected","critical","partial matrix","positive definite","graph","Lovász theta parameter","completion","matrix","Mathematics"],"dc:title":["Ultraconnected and Critical Graphs"],"dc:type":["Thesis"],"thesis:degree_name":["MS"]},"updated_at":"2026-07-24T01:27:16Z"}