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 \(\textbf{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\geq 2\), \(drm(tG)\leq 1+drm(G)\) when \(G\) is connected nonregular and \(drm(tG)\leq m+2-r\) when \(G\) is connected \(r\)-regular of order \(m>2\) and these bounds are tight. \(drm \leq 3\) for other disconnected graphs. Corresponding results for digraphs are also proved.