Sufficient conditions for the N-reconstructibility of all digraphs

Abstract

For a digraph D, we define diam(D) and radius(D) to be the diameter and radius of the underlying graph of D. For a vertex v, the unlabeled digraph D-v together with the degree triple of v is called a degree associated card or dacard of D. The collection of all dacards of D is called the dadeck of D. A digraph is called N-reconstructible if it is determined uniquely by its dadeck. We prove that all digraphs are N-reconstructible if and only if either of the following two classes of digraphs are N-reconstructible. (i). Digraphs D with diam(D) ≤ 2 or diam(D) = diam(D ^c) = 3. (ii). Digraphs D with 2-connected underlying graphs and radius(D) ≤ 2.