TY - JOUR

T1 - On digraphs with prescribed eccentricities

AU - Dankelmann, Peter

AU - Erwin, David

AU - Swart, Henda

N1 - Publisher Copyright:
© Copyright 2018, Charles Babbage Research Centre. All rights reserved.

PY - 2018/2

Y1 - 2018/2

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85045044758&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:85045044758

SN - 0835-3026

VL - 104

SP - 143

EP - 160

JO - Journal of Combinatorial Mathematics and Combinatorial Computing

JF - Journal of Combinatorial Mathematics and Combinatorial Computing

ER -