Sufficient conditions for the nda-reconstructibility of all digraphs
Abstract
A vertex W is called an out-neighbor, in-neighbor or strong neighbor of a vertex /in a digraph D, according as VWis an unpaired arc, Wis an unpaired arc or wand wvare both arcs. The ordered triple (a,b,C) is called the degree triple of V{deti k)), where b and C denote the numbers of out-neighbors, in-neighbors and strong neighbors of /respectively. The ordered triple (C|,C2,C3) is called the neighborhood degree triple (NDT) of v, where C C2 and C3 are respectively the collections of degree triples of the out-neighbors, in-neighbors and strong neighbors of v. The unlabeled subdigraph D-y with which the NDT of /is also given is called an NDA-cardof D. The multiset ofNDA-cards of D is called its NDA-deck. A digraph is called NDA-reconstructible if it is determined uniquely by its NDA-deck. We prove that all digraphs are NDA-reconstructible if all digraphs with 2-connected underlying graphs are NDA-reconstructible. We also point out how two other sufficient conditions follow from this and some other known results. © 2018 Utilitas Mathematica Publishing Incorporated. All rights reserved.
