Diameter of orientations of graphs with given minimum degree

Sheng Bau; Peter Dankelmann

doi:10.1016/j.ejc.2015.03.003

Diameter of orientations of graphs with given minimum degree

Sheng Bau, Peter Dankelmann

Mathematics and Applied Mathematics

University of KwaZulu-Natal

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

15 Citations (Scopus)

Abstract

We show that every bridgeless graph of order n and minimum degree δ has a strongly connected orientation of diameter at most 11δ+1n+9, and such an orientation can be found in polynomial time.

Original language	English
Pages (from-to)	126-133
Number of pages	8
Journal	European Journal of Combinatorics
Volume	49
DOIs	https://doi.org/10.1016/j.ejc.2015.03.003
Publication status	Published - 1 Oct 2015

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2015.03.003

Cite this

@article{a11380eabbba428bb7da534f19d367e7,

title = "Diameter of orientations of graphs with given minimum degree",

abstract = "We show that every bridgeless graph of order n and minimum degree δ has a strongly connected orientation of diameter at most 11δ+1n+9, and such an orientation can be found in polynomial time.",

author = "Sheng Bau and Peter Dankelmann",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier Ltd.",

year = "2015",

month = oct,

day = "1",

doi = "10.1016/j.ejc.2015.03.003",

language = "English",

volume = "49",

pages = "126--133",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Diameter of orientations of graphs with given minimum degree

AU - Bau, Sheng

AU - Dankelmann, Peter

PY - 2015/10/1

Y1 - 2015/10/1

N2 - We show that every bridgeless graph of order n and minimum degree δ has a strongly connected orientation of diameter at most 11δ+1n+9, and such an orientation can be found in polynomial time.

AB - We show that every bridgeless graph of order n and minimum degree δ has a strongly connected orientation of diameter at most 11δ+1n+9, and such an orientation can be found in polynomial time.

UR - http://www.scopus.com/inward/record.url?scp=84926365560&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2015.03.003

DO - 10.1016/j.ejc.2015.03.003

M3 - Article

AN - SCOPUS:84926365560

SN - 0195-6698

VL - 49

SP - 126

EP - 133

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

ER -

Diameter of orientations of graphs with given minimum degree

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this