2026-09-21T22:44:53Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/95378 2023-07-11 col_2142_16340 col_2142_5131 com_2142_16339 com_2142_8903 com_2142_5130

West, Douglas Kostochka, Alexandr Schenck, Hal Molla, Theo Spinoza, Hannah R 2017-03-01T15:49:22Z 2017-03-01T15:49:22Z 2016-12-01 2016-12 A graph is {\it reconstructible} if it is determined by its {\it deck} of unlabeled subgraphs obtained by deleting one vertex; a {\it card} is one of these subgraphs. The {\it Reconstruction Conjecture} asserts that all graphs with at least three vertices are reconstructible. In Chapter $2$ we consider $k$-deck reconstruction of graphs. The {\it $k$-deck} of a graph is its multiset of $k$-vertex induced subgraphs. We prove a generalization of a result by Bollob\'as concerning the $k$-deck reconstruction of almost all graphs, showing that when $\ell \le (1-\epsilon)\frac{n}{2}$, the probability than an $n$-vertex graph is reconstructible from some $\binom{\ell+1}{2}$ of the graphs in the $(n-\ell)$-deck tends to $1$ as $n$ tends to $\infty$. We determine the smallest $k$ such that all graphs with maximum degree $2$ are $k$-deck reconstructible. We prove for $n\ge 26$ that whether a graph is connected is determined by its $(n-3)$-deck. We prove that if $G$ is a complete $r$-partite graphs, then $G$ is $(r+1)$-deck reconstructible (the same holds for $\overline{G}$). In Chapter $3$ we consider degree-associated reconstruction. An $(n-1)$-vertex induced subgraph accompanied with the degree of the missing vertex is called a {\it dacard}. The {\it degree-associated reconstruction number} of a graph $G$ is the fewest number of dacards needed to determine $G$. We provide a tool for reconstructing some graphs from two dacards. We prove that certain families of trees and disconnected graphs can be reconstructed from two dacards. We also determine the degree-associated reconstruction number for complete multipartite graphs and their complements. For such graphs, we also determine the least $s$ such that {\it every} set of $s$ dacards determine the graph. In Chapter $4$ we consider the reconstruction of matrices from principal submatrices. A $(n-\ell)$-by-$(n-\ell)$ principal submatrix is a submatrix formed by deleting $\ell$ rows and columns symmetrically. The {\it matrix reconstruction threshold} $mrt(\ell)$ is the minimum integer $n_0$ such that for $n\ge n_0$ all $n$-by-$n$ matrices are reconstructible from their deck of $(n-\ell)$-by-$(n-\ell)$ principal submatrices. We prove $mrt(\ell) \leq \frac{2}{\ln 2}\ell^2+3\ell$. Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-02-28 without embargo terms The student, Hannah Spinoza, accepted the attached license on 2016-11-30 at 16:59. The student, Hannah Spinoza, submitted this Dissertation for approval on 2016-11-30 at 17:12. This Dissertation was approved for publication on 2016-12-01 at 14:12. DSpace SAF Submission Ingestion Package generated from Vireo submission #10384 on 2017-02-28 at 14:55:02 Made available in DSpace on 2017-03-01T15:49:22Z (GMT). No. of bitstreams: 3 SPINOZA-DISSERTATION-2016.pdf: 711995 bytes, checksum: 7e5c88498aec939a8a2df32190192036 (MD5) LICENSE.txt: 4211 bytes, checksum: db6cd84f8fde9b51cdd073ef0b3a0a9a (MD5) PROQUEST_LICENSE.txt: 4557 bytes, checksum: b1225763f7a2802f350edb05f454583f (MD5) Previous issue date: 2016-12-01 application/pdf http://hdl.handle.net/2142/95378 en Copyright 2016 Hannah Spinoza Graph theory Reconstruction On some problems in reconstruction text text Mathematics Mathematics University of Illinois at Urbana-Champaign Dissertation Ph.D.