On induced subdigraphs of certain distance-defined digraphs

    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