Title

On induced subdigraphs of certain distance-defined digraphs

Authors

Authors

R. C. Brigham; G. Chartrand; R. D. Dutton;P. Zhang

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Util. Math.

Keywords

peripheral vertex; eccentric vertex; boundary vertex; antipodal digraph; eccentric digraph; boundary digraph; GRAPHS; VERTICES; Mathematics, Applied; Statistics & Probability

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.

Journal Title

Utilitas Mathematica

Volume

68

Publication Date

1-1-2005

Document Type

Article

Language

English

First Page

239

Last Page

253

WOS Identifier

WOS:000234383000019

ISSN

0315-3681

Share

COinS