The degree-diameter problem for sparse graph classes

Guillermo Pineda-Villavicencio, David Wood

Research output: Contribution to journalArticleResearchpeer-review

3 Citations (Scopus)

Abstract

The degree-diameter problem asks for the maximum number of vertices in a
graph with maximum degree and diameter k. For xed k, the answer is (k).
We consider the degree-diameter problem for particular classes of sparse graphs, and establish the following results. For graphs of bounded average degree the answer is (k􀀀1), and for graphs of bounded arboricity the answer is (bk=2c), in both cases for xed k. For graphs of given treewidth, we determine the the maximum number of vertices up to a constant factor. Other precise bounds are given for graphs embeddable on a given surface and apex-minor-free graphs.
Original languageEnglish
Pages (from-to)1-20
Number of pages20
JournalThe Electronic Journal of Combinatorics
Volume22
Issue number2
Publication statusPublished - 2015

Keywords

  • degree-diameter problem
  • treewidth
  • arboricity
  • sparse graph
  • surface graph
  • apex-minor-free graph

Cite this