On digraphs with prescribed eccentricities

Peter Dankelmann, David Erwin, Henda Swart

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

Let D be a digraph, ℓ: V(D) → ℕ a labelling that assigns a positive integer to every vertex of D, and let r and d be positive integers satisfying r ≤ min{ℓ(v): v ∈ V(D)} ≤ max{ℓ(v): v ∈ V(D)} ≤ d. If there exists a strongly connected digraph H of out-radius r and diameter d that contains D as an induced subdigraph such that every vertex v of D has out-eccentricity in H equal to ℓ(v), then the labelled digraph D is (r, d) strongly out-eccentric. We prove necessary and sufficient conditions for D to be (r, d) strongly out-eccentric. We establish similar characterizations for oriented graphs and tournaments. Finally, we prove that the subdigraph induced by the vertices of a given eccentricity can have arbitrary structure.

Original languageEnglish
Pages (from-to)143-160
Number of pages18
JournalJournal of Combinatorial Mathematics and Combinatorial Computing
Volume104
Publication statusPublished - Feb 2018

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'On digraphs with prescribed eccentricities'. Together they form a unique fingerprint.

Cite this