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 | |
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