A Size Condition for Diameter Two Orientable Graphs

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

Research output: Contribution to journalArticlepeer-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 languageEnglish
Pages (from-to)527-544
Number of pages18
JournalGraphs and Combinatorics
Volume37
Issue number2
DOIs
Publication statusPublished - Mar 2021

Keywords

  • Diameter
  • Distance
  • Orientation
  • Oriented diameter
  • Oriented graph
  • Size

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'A Size Condition for Diameter Two Orientable Graphs'. Together they form a unique fingerprint.

Cite this