On induced subdigraphs of certain distance-defined digraphs

Abstract

Let G be a nontrivial connected graph. A vertex v is a boundary vertex of a vertex u and of G if d(u, w) ≤ d(u, v) for all neighbors w of v. The boundary digraph BD(G) of G is that digraph with vertex set V(G), where (u, v) is an arc of BD(G) if v is a boundary vertex of u. We investigate the problem of determining which digraphs are the induced subdigraph of the boundary digraph of some graph. We also consider that problem for other distance-related digraphs. For a digraph D, the embedding number of D is the smallest order of a graph G such that D is an induced subdigraph of BD(G). We establish bounds for the embedding numbers of some classes of digraphs.