✦ LIBER ✦

Oriented diameter of graphs with diameter 3

✍ Scribed by Peter K. Kwok; Qi Liu; Douglas B. West

Book ID: 108167475
Publisher: Elsevier Science
Year: 2010
Tongue: English
Weight: 226 KB
Volume: 100
Category: Article
ISSN: 0095-8956
DOI: 10.1016/j.jctb.2009.08.003

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On 3-diameter-stable graphs of diameter

On 3-diameter-stable graphs of diameter 4

✍ Cheng-de Xu; Rui Gu 📂 Article 📅 2010 🏛 Chinese Electronic Periodical Services 🌐 English ⚖ 110 KB

Complexity of approximating the oriented

Complexity of approximating the oriented diameter of chordal graphs

✍ Fedor V. Fomin; Martín Matamala; Ivan Rapaport 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

## Abstract The oriented diameter of a bridgeless connected undirected (__bcu__) graph __G__ is the smallest diameter among all the diameters of strongly connected orientations of __G__. We study algorithmic aspects of determining the oriented diameter of a chordal graph. We (a) construct a linear‐

Minimizing the Oriented Diameter of a Pl

Minimizing the Oriented Diameter of a Planar Graph

✍ Nicole Eggemann; Steven D. Noble 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 182 KB

Diameter vulnerability of graphs

✍ C. Peyrat 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 344 KB

The generalized S-graphs of diameter 3

✍ Jixiang Meng 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 459 KB

A graph is called a generalized S-graph if for every vertex v of G there exists exactly one vertex which is more remote from v than every vertex adjacent to v. A generalized S-graph of diameter 3 is called reducible if there is a pair of diametrical vertices v and t~ such that G-{u, ~} is also a gen

AT-free graphs: linear bounds for the or

AT-free graphs: linear bounds for the oriented diameter

✍ Fedor V Fomin; Martı́n Matamala; Erich Prisner; Ivan Rapaport 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 268 KB

Let G be a bridgeless connected undirected (b.c.u.) graph. The oriented diameter of G, OD(G), is given by OD(G)=min{diam(H ): H is an orientation of G}, where diam(H ) is the maximum length computed over the lengths of all the shortest directed paths in H . This work starts with a result stating tha