Projects per year
Abstract
The degreediameter 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 degreediameter 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 apexminorfree graphs.
graph with maximum degree and diameter k. For xed k, the answer is (k).
We consider the degreediameter 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 apexminorfree graphs.
Original language  English 

Pages (fromto)  120 
Number of pages  20 
Journal  The Electronic Journal of Combinatorics 
Volume  22 
Issue number  2 
Publication status  Published  2015 
Keywords
 degreediameter problem
 treewidth
 arboricity
 sparse graph
 surface graph
 apexminorfree graph
Projects
 1 Finished

Hadwiger's graph colouring conjecture
Wood, D. & Zhou, S.
Australian Research Council (ARC), University of Melbourne
1/01/12 → 30/04/15
Project: Research