Almost minimum diameter orientations of semicomplete multipartite and extended digraphs

Gregory Gutin; Khee Meng Koh; Eng Guan Tay; Anders Yeo

doi:10.1007/s003730200036

Almost minimum diameter orientations of semicomplete multipartite and extended digraphs

Gregory Gutin
, Khee Meng Koh
, Eng Guan Tay
, Anders Yeo

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

11 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. Almost minimum diameter orientations of certain semicomplete multipartite and extended digraphs are considered, several generalizations of results on orientations of undirected graphs are obtained, some conjectures are posed.

Original language	English
Pages (from-to)	499-506
Number of pages	8
Journal	Graphs and Combinatorics
Volume	18
Issue number	3
DOIs	https://doi.org/10.1007/s003730200036
Publication status	Published - 2002
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s003730200036

Cite this

@article{c252a81c091b474c9ef8103fc4326412,

title = "Almost minimum diameter orientations of semicomplete multipartite and extended digraphs",

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. Almost minimum diameter orientations of certain semicomplete multipartite and extended digraphs are considered, several generalizations of results on orientations of undirected graphs are obtained, some conjectures are posed.",

author = "Gregory Gutin and Koh, \{Khee Meng\} and Tay, \{Eng Guan\} and Anders Yeo",

year = "2002",

doi = "10.1007/s003730200036",

language = "English",

volume = "18",

pages = "499--506",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "3",

}

TY - JOUR

T1 - Almost minimum diameter orientations of semicomplete multipartite and extended digraphs

AU - Gutin, Gregory

AU - Koh, Khee Meng

AU - Tay, Eng Guan

AU - Yeo, Anders

PY - 2002

Y1 - 2002

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. Almost minimum diameter orientations of certain semicomplete multipartite and extended digraphs are considered, several generalizations of results on orientations of undirected graphs are obtained, some conjectures are posed.

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. Almost minimum diameter orientations of certain semicomplete multipartite and extended digraphs are considered, several generalizations of results on orientations of undirected graphs are obtained, some conjectures are posed.

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

U2 - 10.1007/s003730200036

DO - 10.1007/s003730200036

M3 - Article

AN - SCOPUS:0036978562

SN - 0911-0119

VL - 18

SP - 499

EP - 506

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 3

ER -

Almost minimum diameter orientations of semicomplete multipartite and extended digraphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this