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 -