✦ LIBER ✦

Directed distance in digraphs: Centers and medians

✍ Scribed by Gary Chartrand; Garry L. Johns; Songlin Tian; Steven J. Winters

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 513 KB
Volume: 17
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190170408

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The directed distance d~D~(u, v) from a vertex u to a vertex v in a strong digraph D is the length of a shortest (directed) u ‐ v path in D. The eccentricity of a vertex v in D is the directed distance from v to a vertex furthest from v. The distance of a vertex v in D is the sum of the directed distances from v to the vertices of D. The center C(D) of D is the subdigraph induced by those vertices of minimum eccentricity, while the median M(D) of D is the subdigraph induced by those vertices of minimum distance. It is shown that for every two asymmetric digraphs D~1~ and D~2~, there exists a strong asymmetric digraph H such that C(H) ≅ D~1~ and M(H) ≅ D~2~, and where the directed distance from C(H) to M(H) and from M(H) to C(H) can be arbitrarily prescribed. Furthermore, if K is a nonempty asymmetric digraph isomorphic to an induced subdigraph of both D~1~ and D~2~, then there exists a strong asymmetric digraph F such that C(F) ≅ D~1~, M(F) ≅ D~2~ and C(F) ∩ M(F) ≅ K. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Distance center and centroid of a median

Distance center and centroid of a median graph

✍ Juhani Nieminen 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 459 KB

Distance connectivity in graphs and digr

Distance connectivity in graphs and digraphs

✍ Balbuena, M. C.; Carmona, A.; Fiol, M. A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 642 KB

Let G = ( V , A ) be a digraph with diameter D # 1. For a given integer 2 5 t 5 D , the t-distance connectivity K ( t ) of G is the minimum cardinality of an z --+ y separating set over all the pairs of vertices z, y which are a t distance d(z, y) 2 t. The t-distance edge connectivity X ( t ) of G i

Maximum directed cuts in acyclic digraph

Maximum directed cuts in acyclic digraphs

✍ Noga Alon; Béla Bollobás; András Gyárfás; Jenő Lehel; Alex Scott 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

## Abstract It is easily shown that every digraph with __m__ edges has a directed cut of size at least __m__/4, and that 1/4 cannot be replaced by any larger constant. We investigate the size of the largest directed cut in __acyclic__ digraphs, and prove a number of related results concerning cuts

Efficient algorithms for centers and med

Efficient algorithms for centers and medians in interval and circular-arc graphs

✍ Sergei Bespamyatnikh; Binay Bhattacharya; Mark Keil; David Kirkpatrick; Michael 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 267 KB

## Abstract The __p__‐center problem is to locate __p__ facilities on a network so as to minimize the largest distance from a demand point to its nearest facility. The __p__‐median problem is to locate __p__ facilities on a network so as to minimize the average distance from a demand point to its c

Maximum directed cuts in digraphs with d

Maximum directed cuts in digraphs with degree restriction

✍ Jenö Lehel; Frédéric Maffray; Myriam Preissmann 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 173 KB

## Abstract For integers __m, k__≥1, we investigate the maximum size of a directed cut in directed graphs in which there are __m__ edges and each vertex has either indegree at most __k__ or outdegree at most __k__. © 2009 Wiley Periodicals, Inc. J Graph Theory

Note on the existence of directed (k + 1

Note on the existence of directed (k + 1)-cycles in diconnected complete k-partite digraphs

✍ R. Balakrishnan; P. Paulraja 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 1 views

A graph is constructed to provide a negative answer to the following question of Bondy: Does every diconnected orientation of a complete k-partite (k 2 5) graph with each part of size at least 2 yield a directed (k + 1)-cycle?