Title

On Induced Subdigraphs Of Certain Distance-Defined Digraphs

Keywords

Antipodal digraph; Boundary digraph; Boundary vertex; Eccentric digraph; Eccentric vertex; Peripheral vertex

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.

Publication Date

11-1-2005

Publication Title

Utilitas Mathematica

Volume

68

Number of Pages

239-253

Document Type

Article

Personal Identifier

scopus

Socpus ID

31144432646 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/31144432646

This document is currently not available here.

Share

COinS