On some problems in reconstruction

Graph theory;Reconstruction

Spinoza, Hannah R

关键词: Graph theory;    Reconstruction;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/95378/SPINOZA-DISSERTATION-2016.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

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$.