Orientations of digraphs almost preserving diameter

Gregory Gutin; Anders Yeo

doi:10.1016/S0166-218X(01)00298-0

Orientations of digraphs almost preserving diameter

Gregory Gutin
, Anders Yeo

Royal Holloway University of London

Research output: Contribution to journal › Article › peer-review

15 Citations (Scopus)

Abstract

An orientation of a digraph D is a spanning subdigraph of D obtained from D by deleting exactly one arc between x and y for every pair x≠y of vertices such that both xy and yx are in D. In this paper, we consider certain well-known classes of strong digraphs, each member D of which has an orientation with diameter not exceeding the diameter of D by more than a small constant.

Original language	English
Pages (from-to)	129-138
Number of pages	10
Journal	Discrete Applied Mathematics
Volume	121
Issue number	1-3
DOIs	https://doi.org/10.1016/S0166-218X(01)00298-0
Publication status	Published - 15 Sept 2002
Externally published	Yes

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/S0166-218X(01)00298-0

Cite this

@article{38f1a3559bf6457985c7514b8e14ae2a,

title = "Orientations of digraphs almost preserving diameter",

abstract = "An orientation of a digraph D is a spanning subdigraph of D obtained from D by deleting exactly one arc between x and y for every pair x≠y of vertices such that both xy and yx are in D. In this paper, we consider certain well-known classes of strong digraphs, each member D of which has an orientation with diameter not exceeding the diameter of D by more than a small constant.",

author = "Gregory Gutin and Anders Yeo",

year = "2002",

month = sep,

day = "15",

doi = "10.1016/S0166-218X(01)00298-0",

language = "English",

volume = "121",

pages = "129--138",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - Orientations of digraphs almost preserving diameter

AU - Gutin, Gregory

AU - Yeo, Anders

PY - 2002/9/15

Y1 - 2002/9/15

N2 - An orientation of a digraph D is a spanning subdigraph of D obtained from D by deleting exactly one arc between x and y for every pair x≠y of vertices such that both xy and yx are in D. In this paper, we consider certain well-known classes of strong digraphs, each member D of which has an orientation with diameter not exceeding the diameter of D by more than a small constant.

AB - An orientation of a digraph D is a spanning subdigraph of D obtained from D by deleting exactly one arc between x and y for every pair x≠y of vertices such that both xy and yx are in D. In this paper, we consider certain well-known classes of strong digraphs, each member D of which has an orientation with diameter not exceeding the diameter of D by more than a small constant.

UR - https://www.scopus.com/pages/publications/84867968246

U2 - 10.1016/S0166-218X(01)00298-0

DO - 10.1016/S0166-218X(01)00298-0

M3 - Article

AN - SCOPUS:84867968246

SN - 0166-218X

VL - 121

SP - 129

EP - 138

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -

Orientations of digraphs almost preserving diameter

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this