On strong distances in oriented graphs

Peter Dankelmann, Henda C. Swart, David P. Day

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)

Abstract

Let D be a strongly connected digraph. The strong distance between two vertices u and v in D, denoted by sd D(u,v) is the minimum size of a strongly connected subdigraph of D containing u and v. The strong eccentricity, se(u), of a vertex u of D, is the strong distance between u and a vertex farthest from u. The minimum strong eccentricity among the vertices of D is the strong radius, srad(D), and the maximum strong eccentricity is the strong diameter, sdiam(D). For asymmetric digraphs (that is, oriented graphs) we present bounds on the strong radius in terms of order and on the strong diameter in terms of order, girth and connectivity.

Original languageEnglish
Pages (from-to)195-201
Number of pages7
JournalDiscrete Mathematics
Volume266
Issue number1-3
DOIs
Publication statusPublished - 6 May 2003
Externally publishedYes

Keywords

  • Directed graph
  • Distance
  • Strong distance

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On strong distances in oriented graphs'. Together they form a unique fingerprint.

Cite this