A Size Condition for Diameter Two Orientable Graphs

Garner Cochran; Éva Czabarka; Peter Dankelmann; László Székely

doi:10.1007/s00373-020-02261-x

A Size Condition for Diameter Two Orientable Graphs

Garner Cochran, Éva Czabarka, Peter Dankelmann, László Székely

Mathematics and Applied Mathematics

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

5 Citations (Scopus)

Abstract

It was conjectured by Koh and Tay [Graphs Combin. 18(4) (2002), 745–756] that for n≥ 5 every simple graph of order n and size at least (n2)-n+5 has an orientation of diameter two. We prove this conjecture and hence determine for every n≥ 5 the minimum value of m such that every graph of order n and size m has an orientation of diameter two.

Original language	English
Pages (from-to)	527-544
Number of pages	18
Journal	Graphs and Combinatorics
Volume	37
Issue number	2
DOIs	https://doi.org/10.1007/s00373-020-02261-x
Publication status	Published - Mar 2021

Keywords

Diameter
Distance
Orientation
Oriented diameter
Oriented graph
Size

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00373-020-02261-x

Cite this

@article{0cd2b1bcc5b94d7db837150aa8dd43bc,

title = "A Size Condition for Diameter Two Orientable Graphs",

abstract = "It was conjectured by Koh and Tay [Graphs Combin. 18(4) (2002), 745–756] that for n≥ 5 every simple graph of order n and size at least (n2)-n+5 has an orientation of diameter two. We prove this conjecture and hence determine for every n≥ 5 the minimum value of m such that every graph of order n and size m has an orientation of diameter two.",

keywords = "Diameter, Distance, Orientation, Oriented diameter, Oriented graph, Size",

author = "Garner Cochran and {\'E}va Czabarka and Peter Dankelmann and L{\'a}szl{\'o} Sz{\'e}kely",

note = "Publisher Copyright: {\textcopyright} 2021, The Author(s), under exclusive licence to Springer Japan KK part of Springer Nature.",

year = "2021",

month = mar,

doi = "10.1007/s00373-020-02261-x",

language = "English",

volume = "37",

pages = "527--544",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "2",

}

TY - JOUR

T1 - A Size Condition for Diameter Two Orientable Graphs

AU - Cochran, Garner

AU - Czabarka, Éva

AU - Dankelmann, Peter

AU - Székely, László

PY - 2021/3

Y1 - 2021/3

N2 - It was conjectured by Koh and Tay [Graphs Combin. 18(4) (2002), 745–756] that for n≥ 5 every simple graph of order n and size at least (n2)-n+5 has an orientation of diameter two. We prove this conjecture and hence determine for every n≥ 5 the minimum value of m such that every graph of order n and size m has an orientation of diameter two.

AB - It was conjectured by Koh and Tay [Graphs Combin. 18(4) (2002), 745–756] that for n≥ 5 every simple graph of order n and size at least (n2)-n+5 has an orientation of diameter two. We prove this conjecture and hence determine for every n≥ 5 the minimum value of m such that every graph of order n and size m has an orientation of diameter two.

KW - Diameter

KW - Distance

KW - Orientation

KW - Oriented diameter

KW - Oriented graph

KW - Size

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

U2 - 10.1007/s00373-020-02261-x

DO - 10.1007/s00373-020-02261-x

M3 - Article

AN - SCOPUS:85098597212

SN - 0911-0119

VL - 37

SP - 527

EP - 544

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 2

ER -

A Size Condition for Diameter Two Orientable Graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this