Neighborhood degrees associated reconstruction of digraphs for Ulam's conjecture

Abstract

In a digraph D, a vertex w is called an out-neighbor, in-neighbor or strong neighbor of/depending on whether VWs an unpaired arc, WV an unpaired arc or Wand WV are both arcs. The ordered triple (a,b,C) is called the degree triple of V, where a, b and C denote the numbers of out-neighbors, in-neighbors and strong neighbors of v respectively. The ordered triple (C1,C2,C3) is called the neighborhood degree triple (NDT) of V, where C1 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-V with which the NDT of V is also given is called an NDA-card of D and it gives the collection of degree triples of the vertices of D. We introduce reconstruction and the reconstruction number of digraphs based on their NDA-cards and some representations for the direction of arcs and exhibit the strength of Ulam's conjecture on reconstruction of graphs, in spite of the failure of Harary's extension of it to digraphs. © 2018 Utilitas Mathematica Publishing Inc. All rights reserved.