Reconstruction Number for Ulam’s Conjecture

Abstract

A vertex-deleted subgraph (subdigraph) of a graph (digraph) $G$ is called a card of $G$. A card of $G$ with which the degree (degree triple) of the deleted vertex is also given is called a degree associated card or dacard of $G$. To investigate the failure of digraph reconstruction conjecture and its effect on Ulam’s conjecture, we study the parameter $\mathbf{\text{degree associated reconstruction number}}$ $drm(G)$ of a graph (digraph) $G$ defined as the minimum number of dacards required in order to uniquely identify $G$. We find $drm$ for some classes of graphs and prove that for $t\ge 2$, $drm(tG)\le 1+drm(G)$ when $G$ is connected nonregular and $drm(tG)\le m+2-r$ when $G$ is connected $r$-regular of order $m>2$ and these bounds are tight. $drm\le 3$ for other disconnected graphs. Corresponding results for digraphs are also proved.