\documentclass[12pt]{article} \usepackage{e-jc} %\specs{}{}{} \usepackage{amsthm,amsfonts,amsmath, amssymb,graphicx,float,enumerate} \usepackage[numbers,sort&compress]{natbib} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \usepackage{verbatim} \usepackage[T1]{fontenc} \renewcommand{\thefootnote}{\arabic{footnote}} \DeclareMathOperator{\dist}{dist} \DeclareMathOperator{\diam}{diam} \newcommand{\arXiv}[1]{arXiv:\,\href{http://arxiv.org/abs/#1}{#1}} \newcommand{\msn}[1]{MR:\,\href{http://www.ams.org/mathscinet-getitem?mr=MR#1}{#1}} \newcommand{\MSN}[2]{MR:\,\href{http://www.ams.org/mathscinet-getitem?mr=MR#1}{#1}} \newcommand{\doi}[1]{doi:\,\href{http://dx.doi.org/#1}{#1}} \newcommand{\cs}[1]{CiteSeer:\,\href{http://citeseerx.ist.psu.edu/viewdoc/summary?doi=#1}{#1}} \newcommand{\Zbl}[1]{Zbl:\,\href{http://www.zentralblatt-math.org/zmath/en/search/?q=an:#1}{#1}} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{conjecture}[theorem]{Conjecture} \newcommand{\thmlabel}[1]{\label{thm:#1}} \newcommand{\thmref}[1]{Theorem~\ref{thm:#1}} \newcommand{\lemlabel}[1]{\label{lem:#1}} \newcommand{\lemref}[1]{Lemma~\ref{lem:#1}} \newcommand{\twolemref}[2]{Lemmas~\ref{lem:#1} and \ref{lem:#2}} \newcommand{\eqnlabel}[1]{\label{eqn:#1}} \newcommand{\figlabel}[1]{\label{fig:#1}} \newcommand{\figref}[1]{Figure~\ref{fig:#1}} \newcommand{\Figref}[1]{Figure~\ref{fig:#1}} \newcommand{\seclabel}[1]{\label{sec:#1}} \newcommand{\secref}[1]{Section~\ref{sec:#1}} \newcommand{\corlabel}[1]{\label{cor:#1}} \newcommand{\corref}[1]{Corollary~\ref{cor:#1}} \newcommand{\proplabel}[1]{\label{prop:#1}} \newcommand{\propref}[1]{Proposition~\ref{prop:#1}} \newcommand{\twopropref}[2]{Propositions~\ref{prop:#1} and \ref{prop:#2}} \newcommand{\conjlabel}[1]{\label{con:#1}} \newcommand{\conjref}[1]{Conjecture~\ref{con:#1}} \newcommand{\GG}{\ensuremath{\mathcal{G}}} \newcommand{\D}{\Delta} \newcommand{\Pl}{\mathcal{P}} \newcommand{\CC}{\mathcal{C}} \newcommand{\PP}{\ensuremath{\mathcal{P}}} \newcommand{\T}{\ensuremath{\mathcal{T}}} \newcommand{\BB}{\overrightarrow{B}} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\N}{\mathbb{N}} \newcommand{\set}[1]{\ensuremath{\protect\{#1\}}} \newcommand{\SET}[1]{\ensuremath{\protect\left\{#1\right\}}} \newcommand{\maxm}[1]{\ensuremath{\protect\max\set{#1}}} \newcommand{\MAXM}[1]{\ensuremath{\protect\max\SET{#1}}} \newcommand{\minm}[1]{\ensuremath{\protect\min\set{#1}}} \newcommand{\MINM}[1]{\ensuremath{\protect\min\SET{#1}}} \newcommand{\bracket}[1]{\ensuremath{\protect\left(#1\right)}} \newcommand{\eps}{\varepsilon} \newcommand{\ceil}[1]{\ensuremath{\protect\lceil{#1}\rceil}} \newcommand{\floor}[1]{\ensuremath{\protect\lfloor{#1}\rfloor}} \newcommand{\Ceil}[1]{\ensuremath{\protect\left\lceil{#1}\right\rceil}} \newcommand{\Floor}[1]{\ensuremath{\protect\left\lfloor{#1}\right\rfloor}} \newcommand{\FloorFrac}[2]{\Floor{\frac{#1}{#2}}} \newcommand{\CeilFrac}[2]{\Ceil{\frac{#1}{#2}}} \newcommand{\ceilFrac}[2]{\ceil{\frac{#1}{#2}}} \newcommand{\Brac}[1]{\ensuremath{\protect\left(#1\right)}} \newcommand{\BracFrac}[2]{\ensuremath{\protect\left(\frac{#1}{#2}\right)}} \newcommand{\quarter}{\ensuremath{\tfrac14}} \newcommand{\half}{\ensuremath{\tfrac12}} \newcommand{\third}{\ensuremath{\tfrac13}} \newcommand{\ninth}{\ensuremath{\tfrac19}} \renewcommand{\geq}{\geqslant} \renewcommand{\leq}{\leqslant} \begin{document} \title{\bf The degree-diameter problem\\ for sparse graph classes} \author{Guillermo Pineda-Villavicencio\thanks{Research supported by a postdoctoral fellowship funded by the Skirball Foundation via the Center for Advanced Studies in Mathematics at Ben-Gurion University of the Negev, and by an ISF grant. Corresponding author.}\\ \small Centre for Informatics and Applied Optimisation\\[-0.8ex] \small Federation University Australia\\[-0.8ex] \small Ballarat, Australia\\ \small\tt work@guillermo.com.au \and David R. Wood\thanks{Research supported by the Australian Research Council.}\\ \small School of Mathematical Sciences\\[-0.8ex] \small Monash University\\[-0.8ex] \small Melbourne, Australia\\ \small\tt david.wood@monash.edu } \date{\dateline{Apr 24, 2014}{May 26, 2015}{}\\ \small Mathematics Subject Classifications: 05C75, 05C10, 05C83} \maketitle %\tableofcontents \begin{abstract} The degree-diameter problem asks for the maximum number of vertices in a graph with maximum degree $\Delta$ and diameter $k$. For fixed $k$, the answer is $\Theta(\Delta^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 $\Theta(\Delta^{k-1})$, and for graphs of bounded arboricity the answer is $\Theta(\Delta^{\floor{k/2}})$, in both cases for fixed $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. \bigskip\noindent \textbf{Keywords:} degree-diameter problem; treewidth; arboricity; sparse graph; surface graph; apex-minor-free graph \end{abstract} \section{Introduction} \seclabel{Intro} Let $N(\Delta,k)$ be the maximum number of vertices in a graph with maximum degree at most $\Delta$ and diameter at most $k$. Determining $N(\Delta,k)$ is called the \emph{degree-diameter} problem and is widely studied, especially motivated by questions in network design; see \citep{MS-EJC05} for a survey. Obviously, $N(\Delta,k)$ is at most the number of vertices at distance at most $k$ from a fixed vertex. For $\D\geq3$ (which we implicitly assume), it follows that $$N(\Delta,k)\;\leq\; M(\D,k)\;:=\;1+\Delta\sum_{i=0}^{k-1}(\Delta-1)^i\;=\;\frac{\D(\D-1)^k-2}{\D-2} %\;\leq\; 3(\Delta-1)^k \enspace.$$ This inequality is called the Moore bound \cite[p.~8]{MS-EJC05}. %The first inequality here is called the Moore bound. %We call the right inequality the \emph{weak Moore bound}, which is particularly useful for asymptotic results, which are the focus of this paper. The best lower bound is $$N(\Delta,k)\geq f(k)\, \Delta^k\enspace,$$ for some function $f$. For example, the de Bruijn graph shows that $N(\Delta,k)\geq\big(\tfrac{\Delta}{2}\big)^k$; see \lemref{deBruijn}. \citet{CG05} established the best known asymptotic bound of $N(\Delta,k)\geq\big(\tfrac{\Delta}{1.59}\big)^k$ for sufficiently large $\Delta$. For a class of graphs \GG, let $N(\Delta,k,\GG)$ be the maximum number of vertices in a graph in \GG\ with maximum degree at most $\Delta$ and diameter at most $k$. We consider $N(\Delta,k,\GG)$ for some particular classes \GG\ of sparse graphs, focusing on the case of small diameter $k$, and large maximum degree $\Delta$. We prove lower and upper bounds on $N(\Delta,k,\GG)$ of the form \begin{equation} \label{MainEquation} f(k)\, \Delta^{ g(k) }\end{equation} for some functions $f$ and $g$. Since $k$ is assumed to be small compared to $\Delta$, the most important term in such a bound is $g(k)$. Thus our focus is on $g(k)$ with $f(k)$ a secondary concern. We first state two straightforward examples, namely bipartite graphs and trees. The maximum number of vertices in a bipartite graph with maximum degree $\Delta$ and diameter $k$ is $f(k)\,\Delta^{k-1}$ for some function $f$; see references \cite[Section 2.4.4]{MS-EJC05} and \citep{Biggs74,Delorme85}. %\propref{BipLineDigraph}. And for trees, it is easily seen that the maximum number of vertices is within a constant factor of $(\Delta-1)^{\floor{k/2}}$, which is a big improvement over the unrestricted bound of $\Delta^k$. Some of the results in this paper can be thought of as generalisations of this observation. The following table summarises our current knowledge, where original results are in bold. \medskip \begin{center} \begin{tabular}{llr} \hline graph class & diameter $k$ & max.\ number of vertices\\\hline general & & $f(k)\,\Delta^k$ \\ {\bf 3-colourable} & $k\geq2$ & $f(k)\,\Delta^k$\\ \bf triangle-free 3-colourable & $k\geq4$ & $f(k)\,\Delta^k$\\ bipartite & & $f(k)\,\Delta^{k-1}$\\ \bf average degree $d$ & & $f(k)\,d\Delta^{k-1}$\\ \bf arboricity $b$ && $f(k,b)\,\Delta^{\floor{k/2}}$\\ \bf treewidth $t$ & odd $k$ & $ct\,(\Delta-1)^{(k-1)/2}$\\ \bf treewidth $t$ & even $k$ & $c\sqrt{t}\,(\Delta-1)^{k/2}$\\ \bf Euler genus $g$ & odd $k$ & $\leq c(g+1)k\,(\Delta-1)^{(k-1)/2}$\\ \bf Euler genus $g$ & even $k$ & $\leq c\sqrt{(g+1)k}\,(\Delta-1)^{k/2}$\\ %planar & $c\,\Delta^{\floor{k/2}}$\\ trees & & $c\,\Delta^{\floor{k/2}}$\\ \hline \end{tabular} \end{center} \medskip First consider the class of graphs with average degree $d$. In this case, we prove that the maximum number of vertices is $f(k)\,d\Delta^{k-1}$ for some function $f$ (see \secref{Degree}). This shows that by assuming bounded average degree we obtain a modest improvement over the standard bound of $(\Delta-1)^k$. A much more substantial improvement is obtained by considering arboricity. The \emph{arboricity} of a graph $G$ is the minimum number of spanning forests whose union is $G$. % That is, a graph $G$ has arboricity at most $q$ if and only if % $E(G)$ can be partitioned $E_1,E_2,\dots,E_q$, such that the % spanning subgraph with edge set $E_i$ is acyclic. \citet{NW-JLMS64} proved that the arboricity of $G$ equals \begin{equation} \label{NashWilliams} \max_{H\subseteq G}\,\big\lceil\tfrac{|E(H)|}{ |V(H)|-1}\big\rceil\enspace, \end{equation} where the maximum is taken over all subgraphs $H$ of $G$. % For an integer $d$, a graph $G$ is $d$-degenerate if every subgraph % of $G$ has minimum degree at most $d$. For example, it follows from Euler's formula that every planar graph has arboricity at most $3$, and every graph with Euler genus $g$ has arboricity at most $O(\sqrt{g})$. More generally, every graph that excludes a fixed minor has bounded arboricity. Note that $\delta\leq d\leq 2b$ for every graph with minimum degree $\delta$, average degree $d$, and arboricity $b$. Arboricity is a more refined measure than average degree, in the sense that a graph has bounded arboricity if and only if every subgraph has bounded average degree. We prove that for a graph with arboricity $b$ the maximum number of vertices is $f(b,k)\,\Delta^{\floor{k/2}}$ for some function $f$ (see \secref{Arboricity}). Thus by moving from bounded average degree to bounded arboricity the $g(k)$ term discussed above is reduced from $k-1$ to $\floor{\frac{k}{2}}$. This result generalises the above-mentioned bound for trees, which have arboricity 1. The dependence on $b$ in $f$ can be reduced by making more restrictive assumptions about the graph. Treewidth is a parameter that measures how tree-like a given graph is. The \emph{treewidth} of a graph $G$ can be defined to be the minimum integer $t$ such that $G$ is a spanning subgraph of a chordal\footnote{A graph is \emph{chordal} if every induced cycle is a triangle.} graph with no $(t+2)$-clique. For example, trees are exactly the connected graphs with treewidth 1. See \citep{Reed97,Bodlaender-TCS98} for background on treewidth. Since the arboricity of a graph is at most its treewidth, bounded treewidth is indeed a more restrictive assumption than bounded arboricity. We prove that the maximum number of vertices in a graph with treewidth $t$ is within a constant factor of $t(\Delta-1)^{(k-1)/2}$ if $k$ is odd, and of $\sqrt{t}(\Delta-1)^{k/2}$ if $k$ is even (and $\Delta$ is large). These results immediately imply the best known bounds for graphs of given Euler genus\footnote{A \emph{surface} is a non-null compact connected 2-manifold without boundary. Every surface is homeomorphic to the sphere with $h$ handles or the sphere with $c$ cross-caps. The sphere with $h$ handles has \emph{Euler genus} $2h$, and the sphere with $c$ cross-caps has \emph{Euler genus} $c$. The \emph{Euler genus} of a graph $G$ is the minimum Euler genus of a surface in which $G$ embeds. See the monograph by \citet{MoharThom} for background on graphs embedded in surfaces.}, and new bounds for apex-minor-free graphs. All these results are presented in \secref{Separators}. %Our final results generalise a number of the above theorems for planar graphs to %so-called apex-minor-free graphs and for graphs embedded on %surfaces other than the sphere. Our results in \secref{3Colour} are of a different nature. There, we describe (non-sparse) graph classes for which the maximum number of vertices is not much different from the unrestricted case. In particular, we prove that for $k\geq2$, there are 3-colourable graphs with $f(k)\,\Delta^k$ vertices, and for for $k\geq4$, there are triangle-free 3-colourable graphs with $f(k)\,\Delta^k$ vertices. These results are in contrast to the bipartite case, in which $f(k)\,\Delta^{k-1}$ is the answer. All undefined terminology and notation is in reference \cite{D05}. % \begin{table}[H] % \caption{Lower and upper bounds on $N(\Delta,k,\GG)$ for various graph % classes $\GG$, where $c>0$ is some constant.} % \begin{tabular}{ll} % \hline % graph class & bound\\ % \hline % average degree $d$ & $cd(c\Delta)^{k-1}$\\ % arboricity $b$& $c(cb\Delta)^{\floor{k/2}}$\\ % genus $g$ & $cg(c\Delta)^{\floor{k/2}}$\\ % planar& \\ % \hline % \end{tabular} % \end{table} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Basic Constructions} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% This section gives some graph constructions that will later be used for proving lower bounds on $N(\Delta,k,\GG)$. Let $\BB(r,k)$ be the de Bruijn digraph\footnote{A \emph{digraph} is a directed graph possibly with loops and possibly with arcs in opposite directions between two vertices.} \citep{deBruijn,Good46}, which has $r^k$ vertices, is $r$-inout-regular\footnote{A digraph is \emph{$r$-inout-regular} if each vertex has indegree $r$ and outdegree $r$ (where a loop at $v$ counts in the indegree and the outdegree of $v$).}, and has strong diameter $k$\footnote{A digraph has \emph{strong diameter} $k$ if for all (not necessarily distinct) vertices $v$ and $w$ there is a directed walk from $v$ to $w$ of length exactly $k$.} \cite[Sec.~IV]{FioYebAle84}. Fiol et al.~\cite[Sec.~IV]{FioYebAle84}, and \citet{ZL87} showed that the $\BB(r,k)$ can be constructed recursively as a line digraph, as we now explain. If $G$ is a digraph with arc set $A(G)$, then the \emph{line digraph} $L(G)$ has vertex set $A(G)$, where $(uv,vw)$ is an arc of $L(G)$ for all distinct arcs $uv,vw\in A(G)$. Let $\BB(r,1)$ be the $r$-vertex digraph in which every arc is present (including loops). Now recursively define $\BB(r,k):=L(\BB(r,k-1))$. \begin{lemma} \lemlabel{deBruijn} For all integers $r\geq 1$ and $k\geq 1$ the de Bruijn graph $B(r,k)$ has $r^k$ vertices, maximum degree at most $2r$, and diameter $k$. Moreover, for $k\geq 2$, there are sets $B_1,\dots,B_{r^{k-1}}$ of vertices in $B(r,k)$, each containing $2r-2$ or $2r$ vertices, such that each vertex of $B(r,k)$ is in exactly two of the $B_i$, and the endpoints of each edge of $B(r,k)$ are in some $B_i$. \end{lemma} \begin{proof} \begin{comment} Let $\BB(r,1)$ be the $r$-vertex digraph in which every arc is present (including loops). Then $\BB(r,1)$ is $r$-inout-regular, and has strong diameter $1$, as claimed. Now recursively define $\BB(r,k):=L(\BB(r,k-1))$. By induction, we may assume that $\BB(r,k-1)$ has $r^{k-1}$ vertices, is $r$-inout-regular, and has strong diameter $k-1$. Thus $\BB(r,k-1)$ has $r^{k}$ edges, implying $\BB(r,k)$ has $r^{k}$ vertices. Consider an arc $uv$ of $\BB(r,k-1)$, which is a vertex of $\BB(r,k)$. Then $uv$ is incident with $r$ outgoing arcs in $\BB(r,k)$, corresponding to the $r$ arcs leaving $v$ in $\BB(r,k-1)$. Similarly, $uv$ is incident with $r$ incoming arcs in $\BB(r,k)$, corresponding to the $r$ arcs entering $u$ in $\BB(r,k-1)$. Hence $\BB(r,k)$ is $r$-inout-regular. To prove that $\BB(r,k)$ has strong diameter $k$, consider two arcs $xy$ and $uv$ of $\BB(r,k-1)$, which are vertices of $\BB(r,k)$. In $\BB(r,k-1)$, there is a directed walk from $y$ to $u$ of length $k-1$. Say $a_1,\dots,a_{k-1}$ are the arcs of such a walk. Then $xy,a_1,\dots,a_{k-1},uv$ is the vertex set of a directed walk of length $k$ in $\BB(r,k)$. Hence $\BB(r,k)$ has strong diameter $k$. \end{comment} Define $B(r,k)$ to be the undirected graph that underlies $\BB(r,k)$ (ignoring loops, and replacing bidirectional arcs by a single edge). Then $B(r,k)$ has $r^k$ vertices, has maximum degree at most $2r$, and has (undirected) diameter $k$ (since loops can be ignored in shortest paths). It remains to prove the final claim of the lemma, where $k\geq 2$. For each vertex $v$ of $\BB(r,k-1)$, let $B_v$ be the set of vertices of $B(r,k)$ that correspond to non-loop arcs incident with $v$ in $\BB(r,k-1)$. Thus $|B_v|$ equals $2r-2$ or $2r$ depending on whether there is a loop at $v$ in $\BB(r,k-1)$. Each vertex of $B(r,k)$ corresponding to an arc $vw$ of $\BB(r,k-1)$ is in exactly two of these sets, namely $B_v$ and $B_w$. The endpoints of each edge of $B(r,k)$ corresponding to a path $uv,vw$ of $\BB(r,k-1)$ are both in $B_v$. These $r^{k-1}$ sets, one for each vertex of $\BB(r,k-1)$, define the desired sets in $B(r,k)$. \end{proof} %Line digraphs are also useful for constructing bipartite graphs. % %\begin{proposition} %\proplabel{BipLineDigraph} %For every even integer $\Delta$ and integer $k\geq 2$, there is a bipartite graph with maximum degree $\Delta$, diameter $k$, and $2(\frac{\Delta}{2})^{k-1}$ vertices. %\end{proposition} % %\begin{proof} Let $G_2$ be the complete bipartite digraph with $\frac{\Delta}{2}$ black vertices and $\frac{\Delta}{2}$ white vertices, with an arc from each black vertex to each white vertex, and an arc from each white vertex to each black vertex. Observe that $G_2$ is $\frac{\Delta}{2}$-inout-regular, has strong diameter $2$, and has $\Delta$ vertices. Now, recursively define the iterated line digraph $G_k:=L(G_{k-1})$ for $k\geq 3$. By the argument in the proof of \lemref{deBruijn}, $G_k$ is $\frac{\Delta}{2}$-inout-regular, has strong diameter $k$, and has $2(\frac{\Delta}{2})^{k-1}$ vertices. Moreover, $G_k$ is bipartite, since $G_2$ is obviously bipartite, and given a 2-colouring of the vertices of $G_{k-1}$, colour black each vertex of $G_k$ that corresponds to an arc from a black vertex to a white vertex in $G_{k-1}$, and colour white each vertex of $G_k$ that corresponds to an arc from a white vertex to a black vertex in $G_{k-1}$. Finally, consider the underlying undirected graph of $G_k$. It is bipartite, has maximum degree $\Delta$, has diameter $k$, and has $2(\frac{\Delta}{2})^{k-1}$ vertices. %\end{proof} % %The well-known bipartite Moore bound says that every bipartite graph has at most $\frac{2}{\Delta-2}((\Delta-1)^k-2)\leq c(\Delta-1)^{k-1}$ vertices; see \cite[Section 2.4.4]{MS-EJC05}. Thus the $f(k)\,\Delta^{k-1}$ bound in \propref{BipLineDigraph} is tight up to the function $f$. The next two lemmas will be useful later. \begin{lemma} \lemlabel{LineGraph} For every integer $q> 1$ there is a $(2q-2)$-regular graph $L$ with $\binom{q+1}{2}$ vertices, containing cliques $L_1,\dots,L_{q+1}$ each of order $q$, such that each vertex in $L$ is in exactly two of the $L_i$, and $L_i\cap L_j\neq\emptyset$ for all $i,j\in[1,q+1]$. \end{lemma} \begin{proof} Let $L$ be the line graph of the complete graph $K_{q+1}$. That is, $V(L):=\{\{i,j\}:1\leq i,j\leq q+1,\, i\neq j\}$, where $L_i:=\{\{i,j\}:1\leq j\leq q+1,\, i\neq j\}$ is a clique for each $i\in[1,q+1]$. The claimed properties are immediate. \end{proof} \begin{lemma} \lemlabel{BipartiteLemma} For all integers $p\geq1$ and $q\geq 1$ and $m\leq (q+1)p$ there is a bipartite graph $T$ with bipartition $C,D$, such that $C$ consists of $m$ vertices each with degree $q$, and $D$ consists of $\binom{q+1}{2}$ vertices each with degree at most $2p$, and every pair of vertices in $C$ have a common neighbour in $D$. \end{lemma} \begin{proof} %If $q=1$ then the star with $m$ leaves satisfies the lemma. Now %assume that $q\geq 2$. By \lemref{LineGraph}, there is a set $D=V(L)$ of size $\binom{q+1}{2}$, containing subsets $D_1,\dots,D_{q+1}$ each of size $q$, such that each element of $D$ is in exactly two of the $D_i$, and $D_i\cap D_j\neq\emptyset$ for all $i,j\in[1,q+1]$. Let $T$ be the graph with vertex set $C\cup D$, where $C$ is defined as follows. For each $i\in[1,q+1]$ add a set $C_i$ of $p$ vertices to $C$, each adjacent to every vertex in $D_i$. Since $|D_i|=q$, each vertex in $C$ has degree $q$. Since each element of $D$ is in exactly two of the $D_i$, each vertex in $D$ has degree $2p$. Consider two vertices $v,w\in C$. Say $v\in C_i$ and $w\in C_j$. Let $x$ be a vertex in $D_i\cap D_j$. Then $x$ is a common neighbour of $v$ and $w$ in $G$. We have proved that $T$ has the desired properties in the case that $m=(q+1)p$. Finally, delete $(q+1)p-m$ vertices from $C$, and the obtained graph has the desired properties. \end{proof} %A number of our constructions employ the following subgraph. \label{TTT} Let $T(\Delta,d,\ell)$ be the rooted tree such that the root vertex has degree $d$, every non-root non-leaf vertex has degree $\Delta$, and the distance between the root and each leaf % equals $\ell$. Note that the number of vertices in $T(\Delta,d,\ell)$ is % \begin{equation} % \label{Tevrtices} % 1+d\sum_{i=0}^{\ell-1} (\Delta-1)^i = 1 + d\Big(1+\frac{\Delta}{\Delta-2}((\Delta-1)^\ell-1\big)\Big) \geq % \enspace. % \end{equation} % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Average Degree} \seclabel{Degree} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% This section presents bounds on the maximum number of vertices in a graph with given average degree. For fixed diameter, the upper and lower bounds are within a constant factor. We have the following rough upper bound for graphs of given minimum degree. \begin{proposition} \proplabel{MinimumDegreeUpperBound} Every graph with minimum degree $\delta$, maximum degree $\Delta$ and diameter $k$ has at most $2\delta(\Delta-1)^{k-1}+1$ vertices. \end{proposition} \begin{proof} Let $v$ be a vertex of degree $\delta$. For $0\leq i\leq k$, let $n_i$ be the number of vertices at distance $i$ from $v$. Thus $n_0=1$ and $n_i\leq \delta(\Delta-1)^{i-1}$ for all $i\geq 1$. In total, $n=\sum_{i=0}^kn_i\leq 1+\sum_{i=1}^k\delta(\Delta-1)^{i-1}= 1 + \delta\,\frac{(\Delta-1)^k-1}{\Delta-2} \leq 1 + 2\delta(\Delta-1)^{k-1}$. \end{proof} Since minimum degree is at most average degree, we have the following corollary. \begin{corollary} \corlabel{AverageDegreeUpperBound} Every graph with average degree $d$, maximum degree $\Delta$ and diameter $k$ has at most $2d(\Delta-1)^{k-1}+1$ vertices. \end{corollary} The following is the main result of this section; it says that \corref{AverageDegreeUpperBound} is within a constant factor of optimal for fixed $k$. % \begin{proposition} % \label{AverageDegreeLowerBound} % For all even $\Delta\geq 4$ and $k\geq 3$ there is a graph with % average degree less than $3$ and at least % $(\frac{\Delta}{2})^{k-1}$ vertices. % \end{proposition} % \begin{proof} % Let $H$ be the $\frac{\Delta}{2}$-regular de Bruijn graph of % diameter $k-2$, which has $(\frac{\Delta}{2})^{k-2}$ vertices. Let % $G$ be the graph obtained from $H$ as follows: for each vertex $v$ % of $H$ add $\frac{\Delta}{2}$ new vertices adjacent to % $v$. Clearly $G$ has diameter $k$. And $G$ has % $(\frac{\Delta}{2})^{k-2}$ vertices of degree $\Delta$, and % $(\frac{\Delta}{2})^{k-1}$ vertices of degree 1. Hence $G$ has % average degree $$\frac{ (\frac{\Delta}{2})^{k-1} + \Delta % (\frac{\Delta}{2})^{k-2} }{ (\frac{\Delta}{2})^{k-1} + % (\frac{\Delta}{2})^{k-2} }<3\enspace.$$ % \end{proof} % \corref{AverageDegreeUpperBound} and % \propref{AverageDegreeLowerBound} together imply that the % maximum number of vertices in a graph with bounded average degree % asymptotically is $(c\Delta)^{k-1}$. \begin{proposition} \proplabel{AverageDegreeLowerBound} For all integers $d\geq 4$ and $k\geq 3$ and $\Delta\geq 2d$ there is a graph with average degree at most $d$, maximum degree at most $\Delta$, diameter at most $k$, and at least $\frac{d}{8}\floor{\frac{\Delta}{4}}^{k-1}$ vertices. \end{proposition} \begin{proof} Let $r:=\floor{\frac{\Delta}{4}}$. Let $q:=\floor{\frac{d}{4}}\geq 2$. Let $p:=\floor{\frac{\Delta}{2}}-r-q+1$. Note that $d\geq 4q$ and $4p\geq \Delta-4q \geq \frac{\Delta}{2}$. Let $B:=B(r,k-2)$ be the graph from \lemref{deBruijn} with maximum degree at most $2r$, diameter $k-2$, and $r^{k-2}$ vertices. Let $L$ be the $(2q-2)$-regular graph from \lemref{LineGraph} with $\binom{q+1}{2}$ vertices, containing cliques $L_1,\dots,L_{q+1}$ each of order $q$, such that each vertex in $L$ is in exactly two of the $L_i$, and $L_i\cap L_j\neq\emptyset$ for all $i,j\in[1,q+1]$. Let $H$ be the cartesian product graph $L\,\square\, B$. Note that $H$ has $\binom{q+1}{2}\,r^{k-2}$ vertices and has maximum degree at most $2q-2+2r$. For $i\in[1,q+1]$ and $v\in V(B)$, let $X_{i,v}$ be the clique $\{(x,v):x\in L_i\}$ in $H$. Since each vertex in $L$ is in exactly two of the $L_i$, each vertex in $H$ is in exactly two of the $X_{i,v}$. Let $G$ be the graph obtained from $H$ as follows: for $i\in[1,q+1]$ and $v\in V(B)$, add an independent set $Y_{i,v}$ of $p$ vertices to $G$ completely adjacent to $X_{i,v}$; that is, every vertex in $Y_{i,v}$ is adjacent to every vertex in $X_{i,v}$. We now prove that $G$ has the claimed properties. The number of vertices in $G$ is $$|V(G)| \geq \sum_{i,v}|Y_{i,v}| =(q+1)r^{k-2} p \geq \tfrac{d}{4}\floor{\tfrac{\Delta}{4}}^{k-2} \tfrac{\Delta}{8} \geq \tfrac{d}{8}\floor{\tfrac{\Delta}{4}}^{k-1} \enspace.$$ To determine the diameter of $G$, let $\alpha$ and $\beta$ be vertices in $G$. Say $\alpha\in X_{i,v}\cup Y_{i,v}$ and $\beta\in X_{j,w}\cup Y_{j,w}$. Let $x$ be a vertex in $L_i\cap L_j$. Let $v=y_1,\dots,y_{\ell}=w$ be a path of length at most $k-2$ in $B$. Then $\alpha,(x,y_1),(x,y_2),\dots,(x,y_\ell),\beta$ is path of length at most $k$ in $G$. Hence $G$ has diameter at most $k$. Consider the maximum degree of $G$. Each vertex in some set $Y_{i,v}$ has degree $|X_{i,v}|=|L_i|=q\leq\Delta$. Each vertex in some set $X_{i,v}$ has degree $2q-2+2r+2p\leq \Delta$. Thus $G$ has maximum degree at most $\Delta$. It remains to prove that the average degree of $G$ is at most $d$. There are $|V(H)|= \binom{q+1}{2}\,r^{k-2}$ vertices of degree at most $\Delta$, and there are $(q+1) r^{k-2}p$ vertices of degree $q$. Thus the average degree is at most $$ \frac{\binom{q+1}{2}\,r^{k-2}\cdot \Delta\;+\; (q+1) r^{k-2}pq}{\binom{q+1}{2}\,r^{k-2} \;+\; (q+1) r^{k-2}p} = \frac{\frac{q}{2} \Delta\;+\; pq}{\frac{q}{2} \;+\; p}$$ Hence it suffices to prove that $q\Delta + 2pq \leq (q + 2p)d$. Since $\Delta\geq 2d$ and $d\geq 4q$, $$d\Delta = \tfrac{d\Delta}{2} + \tfrac{d\Delta}{2} \geq \tfrac{d\Delta}{2} + d^2 \geq 2q\Delta + 4dq\enspace.$$ That is, $2d\Delta - 2q\Delta - 8qd \geq d\Delta- 4qd$. Since $4p\geq \Delta-4q$ and $8q^2\geq 0$, $$8p(d-q)\geq 2(\Delta-4q)(d-q) = 2d\Delta-2q\Delta-8qd+8q^2 \geq d\Delta- 4qd \geq 4q\Delta- 4qd \enspace.$$ That is, $4pd+2qd\geq 2q\Delta + 4pq$, as desired. Hence the average degree of $G$ is at most $d$. \end{proof} Note that for particular values of $k$ and $\Delta$, other graphs can be used instead of the de Bruijn graph in the proof of \propref{AverageDegreeLowerBound} to improve the constants in our results; we omit all these details. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Arboricity} \seclabel{Arboricity} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% This section proves that the maximum number of vertices in a graph with arboricity $b$ is $f(b,k)\cdot\Delta^{\floor{k/2}}$ for some function $f$. Reasonably tight lower and upper bounds on $f$ are established. First we prove the upper bound. \begin{theorem} \thmlabel{ArboricityUpperBound} For every graph $G$ with arboricity $b$, diameter $k$, and maximum degree $\Delta$, $$|V(G)| \leq 4k (2b)^k \Delta^{\floor{k/2}}+1\enspace.$$ \end{theorem} \begin{proof} Let $G_1,\dots,G_b$ be spanning forests of $G$ whose union is $G$. Orient the edges of each component of each $G_i$ towards a root vertex. The choice of the root is arbitrary. Thus each vertex $v$ of $G$ has outdegree at most 1 in each $G_i$; therefore $v$ has outdegree at most $b$ in $G$. Consider an unordered pair of vertices $\{v,w\}$. Let $P$ be a shortest $vw$-path in $G$. Say $P$ has $\ell$ edges. Then $\ell\leq k$. An edge of $P$ oriented in the direction from $v$ to $w$ is called \emph{forward}. If at least $\ceil{\frac{\ell}{2}}$ of the edges in $P$ are forward, then charge the pair $\{v,w\}$ to $v$, otherwise charge $\{v,w\}$ to $w$. Consider a vertex $v$. If some pair $\{v,w\}$ is charged to $v$ then there is path of length $\ell$ from $v$ to $w$ with exactly $i$ forward arcs, for some $i$ and $\ell$ with $\ceil{\frac{\ell}{2}}\leq i\leq \ell\leq k$. Since each vertex has outdegree at most $b$, the number of such paths is at most $\binom{\ell}{i} b^i\Delta^{\ell-i}$. Hence the number of pairs charged to $v$ is at most \begin{align*} \sum_{\ell=1}^k\sum_{i=\ceil{\ell/2}}^\ell\binom{\ell}{i}b^i\Delta^{\ell-i} \;\leq\;& k \sum_{i=\ceil{k/2}}^k\binom{k}{i}b^i\Delta^{k-i}\\ \;=\;& k \sum_{i=0}^{\floor{k/2}}\binom{k}{k-i}b^{k-i}\Delta^{i}\\ \;\leq\;& k\,2^kb^k \sum_{i=0}^{\floor{k/2}}\Delta^{i}\\ \;\leq\;& 2k (2b)^k \Delta^{\floor{k/2}}\enspace. \end{align*} Hence, the total number of pairs, $\binom{n}{2}$, is at most $2k (2b)^k \Delta^{\floor{k/2}}n$. The result follows. % Let $P'$ be $P$ in reverse. Now, $P$ or $P'$ has at most % $\floor{\ell/2}$ backward edges. If $P$ has at most % $\floor{\ell/2}$ backward edges then charge the pair $\{v,w\}$ to % the first edge in $P$ (starting at $v$). On the other hand, if % $P'$ has at most $\floor{\ell/2}$ backward edges then charge the % pair $\{v,w\}$ to the first edge in $P'$ (starting at $w$). \end{proof} % Note that \thmref{ArboricityUpperBound} is tight for $b=1$ % since there are trees with approximately $\Delta^{k/2}$ vertices. %READ THE PROOF BY \citet[Theorem 4.7]{NesOdM-TreeDepth-EJC06} FOR CENTRED COLOURING %--- CAN WE IMPROVE COROLLARY~\ref{MinorUpperBound}? We now show that the upper bound in \thmref{ArboricityUpperBound} is close to being best possible (for fixed $k$). % \begin{lemma} % \lemlabel{BipartiteArboricity} % Let $G$ be a bipartite graph with bipartition $A,B$. If every % vertex in $A$ has degree at most $p$, then $G$ has arboricity at % most $p$. % \end{lemma} % \begin{proof} % Assign each edge one of $p$ colours, such that two edges receive % distinct colours whenever they have an endpoint in $A$ in % common. Each colour class is a star forest. Hence $G$ has % arboricity at most $p$. % % Say $p\leq q$. Let $G'$ be a non-trivial subgraph of $G$ with % % $A':=A\cap V(G')$ and $B':=B\cap V(G')$. If $B'=\emptyset$ % % then % % $|E(G')|=0 \leq p(|V(G')|-1)$. If $|B'|\geq 1$ then % % $|E(G')|\leq % % p|A'|\leq p|A'|+p(|B'|-1)=p(|V(G')|-1)$. Hence $G$ has % % arboricity % % at most $p$ by \eqref{NashWilliams}. % \end{proof} \begin{theorem} \thmlabel{ArboricityLowerBound} For all even integers $b\geq 2$ and $k\geq 4$ and $\Delta \geq b$, such that $\Delta\equiv 2\pmod{4}$ or $b\equiv 0\pmod{4}$, there is a graph $G$ with arboricity at most $b$, maximum degree at most $\Delta$, diameter at most $k$, and at least $\frac{8}{b^2} (\frac{b\Delta}{8})^{k/2}$ vertices. \end{theorem} \begin{proof} Let $q:=\frac{\Delta}{2}$ and $p:=\frac{b}{2}$ and $\ell:=\frac{k}{2}-1$. Then $q$, $p$ and $\ell$ are positive integers. Let $r:=\frac{(q+1)p}{2}$. Then $r$ is a positive integer (since $\Delta\equiv 2\pmod{4}$ or $b\equiv 0\pmod{4}$). Let $B$ be the de Bruijn graph $B(r,\ell)$. By \lemref{deBruijn}, $B$ has diameter $\ell$ and $r^\ell$ vertices. Moreover, there are sets $B_1,\dots,B_{r^{\ell-1}}$ of vertices in $B$, each containing $2r-2$ or $2r$ vertices, such that each vertex of $B$ is in exactly two of the $B_i$, and the endpoints of each edge in $B$ are in some $B_i$. Let $r_i:=|B_i|$. Thus $r_i\leq 2r=(q+1)p$. By \lemref{BipartiteLemma}, for each $i\in [1,r^{\ell-1}]$ there is a bipartite graph $T_i$ with bipartition $B_i,D_i$, such that $B_i$ consists of $r_i$ vertices each with degree $q$, and $D_i$ consists of $\binom{q+1}{2}$ vertices each with degree at most $2p\leq b$, and each pair of vertices in $B_i$ have a common neighbour in $D_i$. Let $G$ be the bipartite graph with bipartition $V(B)\cup D$, where $D:=\cup_i D_i$ and the induced subgraph $G[B_i,D_i]$ is $T_i$. In $G$, each vertex in $V(B)$ has degree $2q\leq\Delta$, and each vertex in $D$ has degree at most $b\leq\Delta$. Thus $G$ has maximum degree $\Delta$. Assign each edge in $G$ one of $b$ colours, such that two edges receive distinct colours whenever they have an endpoint in $D$ in common. Each colour class induces a subgraph in which each component is a star. Hence $G$ has arboricity at most $b$. Observe that $$|V(G)|\geq |D|= r^{\ell-1}\tbinom{q+1}{2} \geq (\tfrac{b\Delta}{8})^{\ell-1}\,\tfrac{\Delta^2}{8} = (\tfrac{b\Delta}{8})^{k/2-2}\,\tfrac{\Delta^2}{8} = \tfrac{8}{b^2} (\tfrac{b\Delta}{8})^{k/2}\enspace. $$ It remains to prove that $G$ has diameter at most $k$. Consider two vertices $v$ and $w$ in $G$. If $v\in D_i$ then let $v'$ be a neighbour of $v$ in $B_i$. If $v\in B_i$ then let $v'$ be $v$. If $w\in D_j$ then let $w'$ be a neighbour of $w$ in $B_j$. If $w\in B_j$ then let $w'$ be $w$. In $B$, there is a $v'w'$-path $P$ of length at most $\ell$. For each edge $xy$ in $P$, both $x$ and $y$ are in some set $B_a$ (see \lemref{deBruijn}). Since $x$ and $y$ have a common neighbour in $T_a$ (by \lemref{BipartiteLemma}), we can replace $xy$ in $P$ by a 2-edge path in $T_a$, to obtain a $v'w'$-path in $G$ of length at most $2\ell$. Possibly adding the edges $vv'$ or $ww'$ gives a $vw$-path in $G$ of length at most $2\ell+2=k$. Hence $G$ has diameter at most $k$. \end{proof} Consider the case of diameter $2$ graphs with arboricity $b$. Every such graph has average degree less than $2b$, and thus has at most $4b\Delta$ vertices by \corref{AverageDegreeUpperBound}. We now show that this upper bound is within a constant factor of optimal. (This result is not covered by \thmref{ArboricityLowerBound} which assumes $k\geq4$.) % \begin{proof} % Let $v$ be a vertex with degree $d$. There are at most % $d(\Delta-1)$ vertices at distance $2$ from $v$. Every vertex is % at distance at most 2 from $v$. Thus $|V(G)|\leq 1+d % +d(\Delta-1)=1+d\Delta$, as desired. % \end{proof} % \begin{proof}[Second Proof] % The square graph $G^2$ is isomorphic to $K_n$. Thus % $$\half n(n-1)=|E(G^2)| % \leq |E(G)|+\sum_{v\in V(G)}\!\!\tbinom{\deg(v)}{2} =\half % \!\!\sum_{v\in V(G)}\!\!\deg(v)^2 \leq \half\Delta \!\!\sum_{v\in % V(G)}\!\!\deg(v) = \half d \Delta n\enspace.$$ Thus $n\leq % 1+d\Delta$, as desired. % \end{proof} \begin{proposition} For all integers $b\geq1$ and even $\Delta\geq 4b$ there is a graph with diameter $2$, arboricity at most $b$, maximum degree $\Delta$, and at least $\frac{b\Delta}{4}$ vertices. \end{proposition} \begin{proof} % If $b=1$ then the star with $\Delta$ leaves satisfies the claim. Now % assume that $b\geq 2$. By \lemref{LineGraph}, there is a $(2b-2)$-regular graph $X$ with $\binom{b+1}{2}$ vertices, containing cliques $X_1,\dots,X_{b+1}$ each of order $b$, such that each vertex in $X$ is in exactly two of the $X_i$, and $X_i\cap X_j\neq\emptyset$ for all $i,j\in[1,q+1]$. Initialise a graph $G$ equal to $X$. For $i\in[1,b+1]$, add an independent set $Y_i$ of $p:=\frac{\Delta}{2}-b+1$ vertices to $G$ completely adjacent to $X_i$. Consider two vertices $v$ and $w$ in $G$. Say $v\in X_i\cup Y_i$ and $w\in X_j\cup Y_j$. Let $x$ be the vertex in $X_i\cap X_j$. If $v=x$ or $x=w$ then $vw$ is an edge in $G$, otherwise $vxw$ is a path in $G$. Thus $G$ has diameter 2. Vertices in each $X_i$ have degree $2b-2+2p=\Delta$ and vertices in each $Y_i$ have degree $b\leq\Delta$. Hence $G$ has maximum degree $\Delta$. The number of vertices in $G$ is more than $(b+1)p =(b+1)( \frac{\Delta}{2} -b+1) \geq \frac{b\Delta}{4}$. To calculate the arboricity of $G$, consider a subgraph $H$ of $G$. Let $x_i:=|X_i\cap V(H)|$ and $y_i:=|Y_i\cap V(H)|$. Since $x_i\leq|X_i|=b$ and $b\geq 2$, $$ \sum_i \tbinom{x_i}{2} =\sum_i \tfrac{x_i(x_i-1)}{2} \leq \sum_i\tfrac{b(x_i-1)}{2} = \sum_i \tfrac{bx_i-b}{2} < (\sum_i \tfrac{bx_i}{2}) -b\enspace.$$ Since $x_iy_i\leq|X_i|y_i= by_i$, $$ \sum_i \tbinom{x_i}{2}+x_iy_i \leq (\sum_i \tfrac{bx_i}{2}+by_i) -b = b \big((\sum_i \tfrac{x_i}{2}+y_i) -1\big) \enspace.$$ Observe that $|E(H)|\leq \sum_i \binom{x_i}{2}+x_iy_i$ and $|V(H)|\geq \sum_i\tfrac{x_i}{2}+y_i$ (since each vertex in $X$ is in exactly two of the $X_i$). Thus $|E(H)| \leq b( |V(H)| - 1 )$, and $G$ has arboricity at most $b$ by \eqref{NashWilliams}. \end{proof} % WE NEED TO PROVE THAT THIS GRAPH HAS ARBORICITY AT MOST $d$ OR % THEREABOUTS. % \begin{proof} % Let $s:=\floor{\frac{d}{5}}$ and % $p:=\floor{\frac{\Delta+1-s^2}{2}}$. It follows that $\Delta\geq % p \geq s^2\geq 2s$. % Let $G$ be the graph defined by % \begin{align*} % V(G) :=& \{ v_{i,i'} : 1\leq i,i'\leq s \} \cup \{ x_{i,\ell} : % 1\leq % i\leq s, 1\leq \ell \leq p \}\\ % E(G) := & \{ v_{i,i'} v_{j,j'} : 1\leq i,i',j,j' \leq s, (i,i') % \neq (j,j') % \} \\ % & \bigcup\{ v_{i,i'} x_{i,\ell}, v_{i',i} x_{i,\ell} : 1\leq % i,i' \leq s, 1\leq \ell\leq p \}\enspace. % \end{align*} % Since $v_{i,i'} v_{j,j'}$ is an edge, $x_{i,\ell} v_{i,i'} % x_{i',\ell'}$ is a path, and $v_{i,i'} v_{i,j} x_{j,\ell}$ is a % path, $G$ has diameter $2$. Observe that $\deg(v_{i,i'}) = s^2-1 % + 2p$ and there are $s^2$ such vertices. Similarly, % $\deg(x_{i,\ell})=2s$, and there are $sp$ such vertices. Both % these degree values are at most $\Delta$. Thus $G$ has maximum % degree at most $\Delta$. And $G$ has average degree % $$\frac{ (s^2-1+2p)s^2 + 2s(sp)}{s^2+sp}\leq % \frac{ s^4 +2ps^2 +2ps^2}{sp}\leq 5s\leq d\enspace.$$ The number of % vertices in $G$ is more than $sp\geq \frac{d-1}{5} \cdot % \frac{\Delta-s^2}{2} \geq \frac{d}{10} \cdot \frac{\Delta}{4}$. % \end{proof} We conclude this section with an open problem about the degree-diameter problem for graphs containing no $K_t$-minor. Every such graph has arboricity at most $ct\sqrt{\log t}$, for some constant $c>0$; see \citep{Kostochka82,Thomason01,Thomason84}. Thus \thmref{ArboricityUpperBound} implies that for every $K_t$-minor-free graph $G$ with diameter $k$ and maximum degree $\Delta\gg t$, $$|V(G)| \leq 4k (c t\sqrt{\log t} )^k \Delta^{\floor{k/2}}.$$ Improving the $f(t,k)$ term in this $f(t,k)\,\Delta^{\floor{k/2}}$ bound is a challenging open problem. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Separators and Treewidth} \seclabel{Separators} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% This section studies a separator-based approach for proving upper bounds in the degree-diameter problem. A \emph{separation} of order $s$ in an $n$-vertex graph $G$ is a partition $(A,S,B)$ of $V(G)$, such that $|A|\leq\frac23 n$ and $|B|\leq\frac23 n$ and $|S|\leq s$ and there is no edge between $A$ and $B$. \citet{FHS95} first used separators to prove upper bounds in the degree--diameter problem. In particular, they implicitly proved that every graph that has a separation of order $s$ has $3s\,M(\Delta,\floor{\frac{k}{2}})$ vertices. The following lemma improves the dependence on $s$ in this result when $k$ is even. We include the proof by \citet{FHS95} for completeness. \begin{lemma} \lemlabel{NewNewSep} Let $G$ be a graph with maximum degree at most $\Delta$, and diameter at most $k$. Assume $(A,S,B)$ is a separation of order $s$ in $G$. Then \begin{equation*} |V(G)|\leq \begin{cases} 3s\,M(\Delta,\frac{k-1}{2}) & \text{ if $k$ is odd}\\ \frac{3}{2}\sqrt{s}\,\Delta(\Delta-1)^{k/2-1} \,+\,3s\,M(\Delta,\frac{k}{2}-1) & \text{ if $k$ is even}\enspace. \end{cases} \end{equation*} \end{lemma} \begin{proof} Let $n:=|V(G)|$. Note that $|A|\geq n-|B|-s\geq\frac{n}{3}-s$. By symmetry, $|B|\geq \frac{n}{3}-s$. We use this fact repeatedly. For $v\in A\cup B$, let $\dist(v,S):=\min\{\dist(v,x):x\in S\}$. If $\dist(v,S)\geq\floor{k/2}+1$ for some $v\in A$ and $\dist(w,S)\geq\floor{k/2}+1$ for some $w\in B$, then $\dist(v,w)\geq2\floor{k/2}+2\geq k+1$, which is a contradiction. Hence, without loss of generality, $\dist(v,S)\leq\floor{k/2}$ for each $v\in A$. By the Moore bound, for each vertex $x\in S$, there are at most $M(\Delta,\floor{k/2})-1$ vertices in $A$ at distance at most $\floor{k/2}$ from $x$. Each vertex in $A$ is thus counted. Hence $$\frac{n}{3}-s\leq|A|\leq s\,M(\Delta,\floor{k/2})-s\enspace,$$ implying $n\leq 3s\,M(\Delta,\floor{k/2})$. This proves the result of \citet{FHS95} mentioned above, and proves the case of odd $k$ in the theorem. Now assume that $k=2\ell$ is even. Suppose on the contrary that $$\frac{n}{3}>\frac{\sqrt{s}}{2}\,\Delta(\Delta-1)^{\ell-1} \,+\,s\,M(\Delta,\ell-1)\enspace.$$ First consider the case in which some vertex in $A$ is at distance at least $\ell+1$ from $S$. Thus every vertex in $B$ is at distance at most $\ell-1$ from $S$. By the Moore bound, $$s\,M(\Delta,\ell-1) -s \geq |B| \geq \frac{n}{3}-s > \frac{\sqrt{s}}{2}\,M(\Delta,\ell) \,+\,s\,M(\Delta,\ell-1) -s \enspace,$$ which is a contradiction. %Thus $$54s(\Delta-1)^{\ell-1}\leq 9\sqrt{s}(\Delta-1)^{\ell}\frac{\sqrt{s}}{2}\,\Delta(\Delta-1)^{\ell-1} \enspace.$$ By symmetry, $|B'|> \frac{\sqrt{s}}{2}\,\Delta(\Delta-1)^{\ell-1}$. Let $P:=\{(x,y):x\in A',y\in B'\}$. For each pair $(x,y)\in P$, some vertex $v$ in $S$ is at distance $\ell$ from both $x$ and $y$. Charge $(x,y)$ to $v$. We now bound the number of pairs in $P$ charged to each vertex $v\in S$. Say $v$ has degree $a$ in $A$ and degree $b$ in $B$. Thus $a+b \leq \Delta$. There are at most $a(\Delta-1)^{\ell-1}$ vertices at distance exactly $\ell$ from $v$ in $A$, and there at most $b(\Delta-1)^{\ell-1}$ vertices at distance exactly $\ell$ from $v$ in $B$. Thus the number of pairs charged to $v$ is at most $$ab(\Delta-1)^{2\ell-2} \leq \quarter(a+b)^2(\Delta-1)^{2\ell-2} \leq \quarter\Delta^2(\Delta-1)^{2\ell-2}\enspace.$$ %The number of pairs in $P$ charged to each vertex in $S$ is at most $\binom{\Delta(\Delta-1)^{\ell-1}}{2}$. Hence \begin{align*} \frac{s}{4}\,\Delta^2(\Delta-1)^{2\ell-2}=\left(\frac{\sqrt{s}}{2}\,\Delta(\Delta-1)^{\ell-1}\right)^2 <|A'|\cdot|B'|=|P| \leq \frac{s}{4}\Delta^2(\Delta-1)^{2\ell-2}\enspace. \end{align*} This contradiction proves that $n\leq\frac{3}{2}\sqrt{s}\,\Delta(\Delta-1)^{\ell-1} \,+\,3s\,M(\Delta,\ell-1)$. \end{proof} %%%%%% \lemref{NewNewSep} can be written in the following convenient form. \begin{lemma} \lemlabel{NewSep} For all $\epsilon>0$ there is a constant $c_\epsilon$ such that for every graph $G$ with maximum degree $\Delta$, diameter $k$, and a separation of order $s$, \begin{equation*} |V(G)|\leq \begin{cases} (3+\epsilon)s(\Delta-1)^{(k-1)/2} & \text{ if $k$ is odd and $\Delta\geq c_\epsilon$}\\ (\frac{3}{2}+\epsilon)\sqrt{s}\,(\Delta-1)^{k/2} & \text{ if $k$ is even and $\Delta\geq c_{\epsilon}\sqrt{s}$} \enspace. \end{cases} \end{equation*} \end{lemma} \begin{proof} First consider the the odd $k$ case. For $\Delta\geq\frac{6}{\epsilon}+2$ we have $3(\tfrac{\Delta}{\Delta-2})\leq3+\epsilon$. Thus, by \lemref{NewNewSep} and the Moore bound, \begin{equation*} |V(G)| \;\leq\; 3s\,(\tfrac{\Delta}{\Delta-2})(\Delta-1)^{(k-1)/2} \;\leq\; (3+\epsilon)s(\Delta-1)^{(k-1)/2}\enspace. \end{equation*} Now consider the even $k$ case. For $\Delta\geq\tfrac{3}{\epsilon}+1$ we have $\tfrac{3}{2}\,\Delta\leq(\tfrac{3}{2}+\tfrac{\epsilon}{2})\,(\Delta-1)$. And for $\Delta\geq \tfrac{9}{\epsilon}\sqrt{s}+2$ we have $3\sqrt{s} \;\leq\; \tfrac{\epsilon}{3}(\Delta-2) \leq \tfrac{\epsilon}{2}(\tfrac{\Delta-1}{\Delta})(\Delta-2)$, implying $3s\,(\tfrac{\Delta}{\Delta-2}) \leq \tfrac{\epsilon}{2}\sqrt{s}(\Delta-1)$. Hence, by \lemref{NewNewSep} and the Moore bound, \begin{align*} |V(G)| &\;\leq\; \tfrac{3}{2}\sqrt{s}\,\Delta(\Delta-1)^{k/2-1}+3s\,(\tfrac{\Delta}{\Delta-2})(\Delta-1)^{k/2-1} \\ &\;\leq\; (\tfrac{3}{2}+\tfrac{\epsilon}{2})\sqrt{s}\,(\Delta-1)^{k/2}+\tfrac{\epsilon}{2}\sqrt{s}(\Delta-1)^{k/2} \\ &\;\leq\; (\tfrac{3}{2}+\epsilon)\sqrt{s}\,(\Delta-1)^{k/2}\enspace. \end{align*} This completes the proof of the lemma. \end{proof} Treewidth is a key topic when studying separators. In particular, every graph with treewidth $t$ has a separation of order $t+1$, and in fact, a converse result holds~\citep{Reed97}. Thus \lemref{NewSep} implies: \begin{theorem} \thmlabel{Treewidth} For all $\epsilon>0$ there is a constant $c_\epsilon$ such that for every graph $G$ with maximum degree $\Delta$, treewidth $t$, and diameter $k$, \begin{equation*} |V(G)|\leq \begin{cases} (3+\epsilon)(t+1)(\Delta-1)^{(k-1)/2} & \text{ if $k$ is odd and $\Delta\geq c_\epsilon$}\\ (\frac{3}{2}+\epsilon)\sqrt{t+1}\,(\Delta-1)^{k/2} & \text{ if $k$ is even and $\Delta\geq c_{\epsilon}\sqrt{t+1}$} \enspace. \end{cases} \end{equation*} \end{theorem} Note that \thmref{Treewidth} in the case of odd $k$ can also be concluded from a result by \citet[Theorem~3.2]{GPRS01}. Our original contribution is for the even $k$ case. We now show that both upper bounds in \thmref{Treewidth} are within a constant factor of optimal. \begin{proposition} \proplabel{TreewidthConstruction} For all integers $k\geq 1$ and $t\geq 2$ and $\Delta$ there is a graph $G$ with maximum degree $\Delta$, diameter $k$, treewidth at most $t$, and \begin{equation*} |V(G)|\geq \begin{cases} \half(t+1)(\Delta-1)^{(k-1)/2} & \text{ if $k$ is odd and $\Delta\geq 2t-2$}\\ \half\sqrt{t+1}\,(\Delta-1)^{k/2} & \text{ if $k$ is even and $\Delta\geq 4\sqrt{2t}$}\enspace. \end{cases} \end{equation*} \end{proposition} \begin{proof} First consider the case of odd $k$. Let $T$ be the rooted tree such that the root vertex has degree $\Delta-t$, every non-root non-leaf vertex has degree $\Delta$, and the distance between the root and each leaf equals $\frac{k-1}{2}$. Since $t\geq2$ and $\frac{\Delta-t}{\Delta-2}\geq\frac{1}{2}$, \begin{align*} |V(T)|\;=\; 1+(\Delta-t)\sum_{i=0}^{(k-3)/2} (\Delta-1)^i & \;=\; \frac{t-2+(\Delta-t)(\Delta-1)^{(k-1)/2}}{\Delta-2}\\ &\;\geq\; \frac{1}{2}(\Delta-1)^{(k-1)/2} \enspace. \end{align*} Take $t+1$ disjoint copies of $T$, and add a clique on their roots. This graph is chordal with maximum clique size $t+1$. Thus it has treewidth $t$. The maximum degree is $\Delta$ and the number of vertices is at least $\half(t+1)(\Delta-1)^{(k-1)/2}$. Now consider the case of even $k$. Let $q$ be the maximum integer such that $\binom{q+1}{2}\leq t+1$. Thus $2\leq q\leq\sqrt{2t}\leq \frac{\Delta}{4}$ and $q+1\geq\sqrt{t+1}$. Let $T$ be the tree, rooted at $r$, such that $r$ has degree $\Delta-q$, every non-leaf non-root vertex has degree $\Delta$, and the distance between $r$ and each leaf is $\frac{k}{2}-1$. Since $q\geq 2$ and $\frac{\Delta-q}{\Delta-2}\geq\half$, \begin{align*} |V(T)|\;=\; 1+(\Delta-q)\sum_{i=0}^{k/2-2} (\Delta-1)^i \;& =\; \frac{q-2+(\Delta-q)(\Delta-1)^{k/2-1}}{\Delta-2}\\ &\geq\; \frac{1}{2}(\Delta-1)^{k/2-1} \enspace. \end{align*} By \lemref{LineGraph}, there is a $(2q-2)$-regular graph $L$ with $\binom{q+1}{2}$ vertices, containing cliques $L_1,\dots,L_{q+1}$ each of order $q$, such that each vertex in $L$ is in exactly two of the $L_i$, and $L_i\cap L_j\neq\emptyset$ for all $i,j\in[1,q+1]$. Let $G$ be the graph obtained from $L$ as follows. For each $i\in [1,q+1]$, add $\Delta-2(q-1)$ disjoint copies of $T$ (called $i$-copies), where every vertex in $L_i$ is adjacent to the roots of the $i$-copies of $T$, as illustrated in \figref{EvenTreewidth}. It is easily verified that $G$ has maximum degree $\Delta$. Consider a vertex $v$ in some $i$-copy of $T$ or in $L_i$, and a vertex $w$ in some $j$-copy of $T$ or in $L_j$. Let $x$ be in $L_i\cap L_j$. Then $\dist(v,x)\leq\frac{k}{2}$ and $\dist(w,x)\leq\frac{k}{2}$, implying $\dist(v,w)\leq k$. Hence $G$ has diameter at most $k$. Let $G'$ be the supergraph of $G$ obtained by adding a clique on $V(L)$. Thus $G'$ is chordal with maximum clique size $\binom{q+1}{2}\leq t+1$. Hence $G$ has treewidth at most $t$. The number of vertices in $G$ is at least $(q+1)(\Delta-2q+2)|V(T)|\geq\sqrt{t+1}\cdot\frac{\Delta}{2}\cdot(\Delta-1)^{k/2-1}$. %Here, $q+1>\sqrt{t+1}$ since $\binom{q+2}{2}>t+1$, and $\Delta-2q+2\geq\frac{\Delta}{2}$ since $\Delta\geq 4t\geq 4q$. \end{proof} \begin{figure}[!ht] \begin{center} \includegraphics{EvenTreewidth} \end{center} \caption{\figlabel{EvenTreewidth}Construction in \propref{TreewidthConstruction} for even $k$. Here $\Delta=4$ and $k=8$ and $t=2$.} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\section{Graphs on Surfaces} %\seclabel{Surfaces} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% We now consider the degree-diameter problem for graphs with given Euler genus. Note that the case of planar graphs has been widely studied \citep{HS93,FHS95,FHS98,Tis12,Tis12a,NPW}. %All the results for planar graphs have been obtained using separators. %For a surface $\Sigma$, let $\GG(\Sigma)$ be the class of graphs embeddable in $\Sigma$, and let $N(\Delta,k,\Sigma):=N(\Delta,k,\GG(\Sigma))$. \citet{SS04} proved that for every graph $G$ with Euler genus $g$, \begin{equation} \label{SS04} %c_1\Delta^{\floor{k/2}} \leq N(\Delta,k,\Sigma)\leq |V(G)| \leq c(g+1)k\,(\Delta-1)^{\floor{k/2}}\enspace, \end{equation} for some absolute constant $c$. % $c_1,c_2$. %Graphs embeddable on a fixed surface exclude a fixed apex graph as a minor \citep{Eppstein-Algo00}. Thus \thmref{ExcludeApex} is applicable. In fact, %We improve the upper bound in \thmref{SS04} for even $k$ and improve the lower bound in \thmref{SS04} for odd $k$. First the upper bound: \citet{Eppstein-Algo00} proved that every graph with Euler genus $g$ and diameter $k$ has treewidth at most $c(g+1)k$ for some absolute constant $c$, and Dujmovic et al.~\cite{DujMorWoo13} proved the explicit bound of $(2g+3)k$. \thmref{Treewidth} thus implies the upper bound in \eqref{SS04} and improves upon it when $k$ is even: \begin{theorem} For all $\epsilon>0$ there is a constant $c_\epsilon$ such that for every graph $G$ with Euler genus $g$, maximum degree $\Delta$ and diameter $k$, \begin{equation*} |V(G)|\leq \begin{cases} (3+\epsilon)((2g+3)k+1)(\Delta-1)^{(k-1)/2} & \text{for odd $k$ and $\Delta\geq c_\epsilon$}\\ (\frac{3}{2}+\epsilon)\sqrt{(2g+3)k+1}\,(\Delta-1)^{k/2} & \text{for even $k$ and $\Delta\geq c_{\epsilon}\sqrt{(2g+3)k+1}$}. %\enspace. \end{cases} \end{equation*} \end{theorem} In our companion paper~\citep{NPW} we further investigate the degree-diameter problem for graphs on surfaces, providing an improved upper bound and a new lower bound. To obtain an upper bound of the form $n\leq f(k)\,\Delta^{\floor{k/2}}$ using the separator-based approach, one needs a separation of order bounded by a function of the graph's diameter. In some sense, the graphs that have a separation of bounded order are precisely the graphs with bounded treewidth. See Reed's survey \citep{Reed97} for a precise statement here. Thus the separator-based method only works for graphs whose treewidth is bounded by a function of their diameter. The minor-closed graph classes with this property are precisely those that exclude a fixed apex graph as a minor \citep{Eppstein-Algo00}. Here a graph $H$ is \emph{apex} if $H-v$ is planar for some vertex $v$ of $H$. For example, $K_5$ and $K_{3,3}$ are apex. \citet{Eppstein-Algo00} proved that for some apex graph $H$ and some function $f$ (depending on $H$), the treewidth of every $H$-minor-free graph $G$ is at most $f(\diam(G))$. This is called the \emph{diameter-treewidth} or \emph{bounded local treewidth} property; also see \citep{DH-SJDM04,DH-Algo04,Grohe-Comb03,DujMorWoo13}. \citet{DH-SODA04} strengthened Eppstein's result by showing that one can take $f(k)=ck$ for some constant $c=c(H)$. Thus the next result follows from \thmref{Treewidth}. \begin{theorem} \thmlabel{ExcludeApex} For every fixed apex graph $H$ there is a constant $c=c(H)$, such that for every $H$-minor-free graph $G$ with diameter $k$, \begin{equation*} |V(G)| \leq \begin{cases} ck\,(\Delta-1)^{(k-1)/2}&\text{ if $k$ is odd}\\ c\sqrt{k}\,(\Delta-1)^{k/2}&\text{ if $k$ is even and $\Delta\geq c\sqrt{k}$}\enspace. \end{cases} \end{equation*} \end{theorem} As discussed above, for minor-closed classes, \thmref{ExcludeApex} is the strongest possible result that can be obtained using the separator-based method. \section{3-Colourable and Triangle-Free Graphs} \seclabel{3Colour} As mentioned in the introduction, it is well known that the maximum number of vertices in a bipartite graph is $f(k)\,\Delta^{k-1}$. We now show that this bound does not hold for the more general class of 3-colourable graphs. In fact, we construct 3-colourable graphs where the number of vertices is within a constant factor of the Moore bound. First note that \citet{KS02} (building on the work of \citet{HE72}) proved that for large $k\gtrsim\log r$, the de Bruijn graph $B(r,k)$, which roughly has $\big(\tfrac{\Delta}{2}\big)^k$ vertices, is 3-colourable. The constructions below have the advantage of not assuming that $k$ is large. In what follows a \emph{pseudograph} is an undirected graph possibly with loops. A loop at a vertex $v$ counts for 1 in the degree of $v$. A pseudograph $H$ is \emph{$k$-good} if for all (not necessarily distinct) vertices $v$ and $w$ there is a $vw$-walk of length exactly $k$ in $H$. Given pseudographs $H_1$ and $H_2$, the \emph{direct product} graph $H_1\times H_2$ has vertex set $V(H_1)\times V(H_2)$, where $(v,x)(w,y)\in E(H_1\times H_2)$ if and only if $vw\in E(H_1)$ and $xy\in E(H_2)$. \begin{lemma} \lemlabel{Product} Let $H_1$ and $H_2$ be $k$-good pseudographs with maximum degree $\Delta_1$ and $\Delta_2$ respectively. Then $H_1\times H_2$ has $|V(H_1)|\cdot |V(H_2)|$ vertices, maximum degree $\Delta_1\Delta_2$, and diameter at most $k$. Moreover, if $H_2$ is loopless and $c$-colourable, then $H_1\times H_2$ is $c$-colourable. \end{lemma} \begin{proof} Clearly $H_1\times H_2$ has $|V(H_1)|\cdot |V(H_2)|$ vertices and maximum degree $\Delta_1\,\Delta_2$. Let $(v,x)$ and $(w,y)$ be distinct vertices of $G$. To prove that $G$ has diameter at most $k$, we construct a $(v,x)(w,y)$-walk of length at most $k$ in $G$. Since $H_1$ is $k$-good, there is a walk $v=v_0,v_1,\dots,v_k=w$ of length $k$ in $H_1$. Since $H_2$ is $k$-good, there is a walk $x=x_0,x_1,\dots,x_k=y$ of length $k$ in $H_2$. Thus $(v,x)=(v_0,x_0),(v_1,x_1),\dots,(v_k,x_k)=(w,y)$ is a walk of length $k$ between $(v,x)$ and $(w,y)$ in $H_1\times H_2$. Hence $H_1\times H_2$ has diameter at most $k$. Finally, colouring each vertex $(v,x)$ of $H_1\times H_2$ by the colour assigned to $x$ in a $c$-colouring of $H_2$ gives a $c$-colouring of $H_1\times H_2$. \end{proof} \begin{lemma} \lemlabel{K3} $K_3$ is $k$-good for all $k\geq 2$. \end{lemma} \begin{proof} Let $v,w\in V(K_3)=\{0,1,2\}$. If there is a $vw$-walk of length $k-2$, then there is a $vw$-walk of length $k$ (just repeat one edge twice). Thus the claim follows from the $k=2$ and $k=3$ cases. Without loss of generality, $v=0$. For $k=2$, one of $010$, $021$ and $012$ is a $vw$-walk of length 2. For $k=3$, one of $0120$, $0121$ and $0102$ is a $vw$-walk of length 3. \end{proof} To obtain results for triangle-free graphs we use the following: \begin{lemma} \lemlabel{C5} $C_5$ is $k$-good for all $k\geq 4$. \end{lemma} \begin{proof} Say $V(C_5)=\{0,1,2,3,4\}$ and $E(C_5)=\{01,12,23,34,40\}$. Let $v,w\in V(C_5)$. If there is a $vw$-walk of length $k-2$, then there is a $vw$-walk of length $k$ (just repeat one edge twice). Thus the claim follows from the $k=4$ and $k=5$ cases. Without loss of generality, $v=0$. For $k=4$, one of $01010$, $04321$, $01212$, $04343$ and $01234$ is a $vw$-walk of length 4. For $k=5$, one of $012340$, $040101$, $043232$, $012323$ and $010404$ is a $vw$-walk of length 5. \end{proof} \twolemref{Product}{K3} imply: \begin{lemma} \lemlabel{ThreeColourable} Let $H$ be a $k$-good pseudograph with maximum degree $\Delta$ for some $k\geq 2$. Then $H\times K_3$ is a 3-colourable graph with $3|V(H)|$ vertices, maximum degree $2\Delta$, and diameter at most $k$. \end{lemma} \begin{lemma} \lemlabel{TriangleFree} Let $H$ be a $k$-good pseudograph with maximum degree $\Delta$ for some $k\geq 4$. Then $H\times C_5$ is a 3-colourable triangle-free graph with $5|V(H)|$ vertices, maximum degree $2\Delta$, and diameter at most $k$. \end{lemma} \begin{proof} For any graph $G$ (without loops), if $H\times G$ contains a triangle $(a,u)(b,v)(c,w)$, then $uvw$ is a triangle in $G$ (even if $H$ has loops). Since $C_5$ is triangle-free, $H\times C_5$ is triangle-free. Thus \twolemref{Product}{C5} imply the claim. \end{proof} For particular values of $\Delta$ and $k$, various constructions for the degree-diameter problem can be used in the following lemma to give large 3-colourable and triangle-free graphs. \begin{proposition} Let $H$ be a graph with maximum degree $\Delta$ and diameter $k\geq 2$. Then there is a 3-colourable graph with $3|V(H)|$ vertices, maximum degree $2\Delta+2$ and diameter at most $k$. Moreover, if $k\geq 4$ then there is a 3-colourable triangle-free graph with $5|V(H)|$ vertices, maximum degree $2\Delta+2$, and diameter at most $k$. \end{proposition} \begin{proof} Let $H'$ be the pseudograph obtained from $H$ by adding a loop at each vertex. Thus $H'$ is $k$-good and has maximum degree $\Delta+1$. \twolemref{ThreeColourable}{TriangleFree} imply that $H'\times K_3$ and $H'\times C_5$ satisfy the claims. \end{proof} This result implies that for fixed $k\geq2$ and $\Delta\gg k$, the maximum number of vertices in a 3-colourable graph is within a constant factor of the unrestricted case. And the same conclusion holds for $k\geq4$ for 3-colourable triangle-free graphs. We now give a concrete example: \begin{theorem} For all integers $\Delta\geq 4$ and $k\geq 2$, there is a 3-colourable graph with $3\floor{\frac{\Delta}{4}}^{k}$ vertices, maximum degree at most $\Delta$, and diameter at most $k$. Moreover, if $k\geq 4$ then there is a 3-colourable triangle-free graph with $5\floor{\frac{\Delta}{4}}^{k}$ vertices, maximum degree at most $\Delta$, and diameter at most $k$. \end{theorem} \begin{proof} Let $r:=\floor{\frac{\Delta}{4}}$. Let $H$ be the undirected pseudograph underlying the de Bruijn digraph $\overrightarrow{B}(r,k)$ including any loops. \lemref{deBruijn} shows that $H$ has $r^k$ vertices, maximum degree at most $2r$, and is $k$-good. \lemref{ThreeColourable} shows that $H\times K_3$ satisfies the first claim. \lemref{TriangleFree} implies that $H\times C_5$ satisfies the second claim. \end{proof} %\journalarxiv{In the expanded version of this paper \citep{PW13}, we give ad-hoc constructions of triangle-free graphs with diameter 2 and 3, where the number of vertices is $\Omega(\Delta^2)$ and $\Omega(\Delta^3)$ respectively, which is within a constant factor of the Moore bound.} We now give ad-hoc constructions of triangle-free graphs with diameter 2 and 3. These lower bounds are within a constant factor of the Moore bound. Let $\mathbb{Z}_p$ be the cyclic group with $p$ elements. For $a,b\in\mathbb{Z}_p$, let $\dist(a,b):=\min\{a-b,b-a\}$. Here, as always, addition and subtraction are in the group, so $\dist(a,b)\geq0$. \begin{proposition} \proplabel{TriangleFreeDiameter2} For all $\Delta\geq 20$ there is a triangle-free graph with diameter $2$, maximum degree at most $\Delta$, and at least $(2\floor{\frac{\Delta+4}{8}}+2)^2$ vertices. \end{proposition} \begin{proof} Let $p:=2\floor{\frac{\Delta+4}{8}}+2$. Thus $p\geq 8$ is even. %Let $H$ be the graph with vertex set $\mathbb{Z}_p$, where $ab\in E(H)$ whenever $\dist(a,b)\not\in\{0,2\}$. Observe that every pair of distinct vertices in $H$ have a common neighbour. Let $G$ be a graph with vertex set $\mathbb{Z}_p^2$. Thus $|V(G)|=(2\floor{\frac{\Delta+4}{8}}+2)^2$. %Think of the vertices as being in a $p \times p$ grid in the plane. %, as illustrated in Figure~\ref{TriangleFreeDiameter2}. %For each vertex $v$, let $(v_1,v_2)$ be the coordinates of $v$. For distinct vertices $v$ and $w$, define integers $a \leq b$ so that $\{a,b\} = \{ |v_1 - w_1|, |v_2 - w_2| \}$. Then $vw \in E(G)$ if and only if $a=1$ and $b \neq 2$. Let $(v_1,v_2)$ denote a vertex $v$ in $G$. For distinct vertices $v$ and $w$, define the \emph{$vw$-vector} to be $(a,b)$, where $a \leq b$ and $\{a,b\} = \{ \dist(v_1,w_1), \dist(v_2,w_2) \}$. Then $vw \in E(G)$ if and only if $a=1$ and $b\neq 2$. Observe that $G$ is $4(p-3)$-regular, and $4(p-3)\leq \Delta$. We now show that the distance between distinct vertices $v,w$ in $G$ is at most 2. Consider the following cases for the $vw$-vector ($a,b)$, where without loss of generality, $(a,b) = ( \dist(v_1,w_1), \dist(v_2,w_2) )$: Case $(0,\geq 1)$: Since $p\geq 8$, there exists $y\in\mathbb{Z}_p$ such that $\dist(v_2,y)\not\in\{0,2\}$ and $\dist(w_2,y)\not\in\{0,2\}$. Then $(v_1+1,y)=(w_1+1,y)$ is a common neighbour of $v$ and $w$. Case $(1, 2)$: Since $p\geq 8$, there exists $x\in\mathbb{Z}_p$ such that $\dist(v_1,x)\not\in\{0,2\}$ and $\dist(w_1,x)\not\in\{0,2\}$. Since $\dist(v_2,w_2)=2$ there exists $y\in\mathbb{Z}_p$ such that $\dist(v_2,y)=\dist(w_2,y)=1$. Then $(x,y)$ is a common neighbour of $v$ and $w$. Case $(1,\neq 2)$: Then $v$ and $w$ are adjacent. Case $(\geq 2, \geq 2)$: Since $p\geq 8$, there exists $x\in\mathbb{Z}_p$ such that $\dist(w_1,x)=1$ and $\dist(v_1,x)\not\in\{0,2\}$. Similarly, there exists $y\in\mathbb{Z}_p$ such that $\dist(w_2,y)\not\in\{0,2\}$ and $\dist(y,v_1)=1$. Then $(x,y)$ is a common neighbour of $v$ and $w$. Suppose on the contrary that $G$ contains a triangle $T$. For each edge $uv$ of $T$, we have $\dist(u_i,v_i)=1$ for some $i\in[1,2]$. In this case, say $uv$ is \emph{type} $i$. Since there are three pairs of vertices in $T$ and only two types, two pairs of vertices in $T$ have the same type. Say $T=uvw$. Without loss of generality, $uv$ and $vw$ are both type 1. That is, $\dist(u_1,v_1)=1$ and $\dist(v_1,w_1)=1$. Thus $\dist(u_1,w_1)\in\{0,2\}$, in which case $uw\not\in E(G)$. This contradiction shows that $G$ contains no triangle. \end{proof} \begin{proposition} \proplabel{TriangleFreeDiameter3} For all $\Delta\geq 42$ there is a triangle-free graph with diameter $3$, maximum degree at most $\Delta$, and at least $(2\floor{\frac{\Delta+6}{12}}+4)^3$ vertices. \end{proposition} \begin{proof} Let $p:=2\floor{\frac{\Delta+6}{12}}+4$. Thus $p\geq 12$ is even. Let $H$ be the graph with vertex set $\mathbb{Z}_p$, where $ab\in E(H)$ whenever $\dist(a,b)\geq 3$. Observe that every pair of vertices in $H$ have a common neighbour (since $p\geq 12$). Define a graph $G$ with vertex set $V(G) :=\mathbb{Z}_p^3$. Thus $|V(G)|=p^3$. Let $(v_1,v_2,v_3)$ denote a vertex $v$ in $G$. For distinct vertices $v$ and $w$, define the \emph{$vw$-vector} to be $(a,b,c)$, where $a \leq b\leq c$ and $\{a,b,c\} = \{ \dist(v_1,w_1), \dist(v_2,w_2), \dist(v_3,w_3) \}$. Then $vw \in E(G)$ if and only if $a=0$ and $b=1$ and $c \geq 3$. Observe that $G$ is $6(p-5)$-regular, and $6(p-5)\leq \Delta$. We now show that the distance between distinct vertices $v,w$ in $G$ is at most 3. Consider the following cases for the $vw$-vector, where without loss of generality, $(a,b,c) = ( \dist(v_1,w_1), \dist(v_2,w_2), \dist(v_3,w_3) )$: % A Case $(0,0,\geq 1)$: Let $u$ be a common neighbour of $v_3$ and $w_3$ in $H$. Then $(v_1+1,v_2,u)=(w_1+1,w_2,u)$ is a common neighbour of $v$ and $w$. % B Case $(0,1,1)$: Then $(v_1+3,w_2,v_3)=(w_1+3,w_2,v_3)$ is a common neighbour of $v$ and $w$. % C Case $(0,1,2)$: Let $y$ be a common neighbour of $v_2$ and $w_2$ in $H$. Since $\dist(v_3,w_3)=2$, there is an element $z$ such that $\dist(v_3,z)=\dist(w_3,z)=1$. Then $(v_1,y,z)=(w_1,y,z)$ is a common neighbour of $v$ and $w$. % D Case $(0,1,\geq 3)$: Then $v$ and $w$ are adjacent. % F Case $(0,\geq 2,\geq 2)$: Since $\dist(v_2, w_2)\geq 2$, there is an element $y\in\{w_2-1,w_2+1\}$ such that $\dist(v_2,y)\geq 3$. Similarly, $\dist(w_3,z)\geq 3$ for some $z\in\{v_3-1,v_3+1\}$. Then $(v_1,y,z)$ is a common neighbour of $v$ and $w$. % J Case $(1,\geq 1,\geq 1)$: Since $v_2\neq w_2$, there is an element $u\in\{w_2,w_2+2,w_2-2\}$ such that $\dist(v_2,u)\geq 3$. Let $u'$ be such that $\dist(u,u')=\dist(w_2,u')=1$. Let $z$ be a common neighbour of $v_3$ and $z_3$ in $H$. Then $$(v_1,v_2,v_3)(w_1,u,v_3)(w_1,u',z)(w_1,w_2,w_3)$$ is a $vw$-path of length 3. % K Case $(\geq 2, \geq 2, \geq 2)$: Since $p\geq 6$ and $\dist(v_1,w_1)\geq2$, there exists $x\in\mathbb{Z}_p$ such that $\dist(w_1,x)=1$ and $\dist(v_1,x)\geq 3)$. Similarly, there exists $y,z\in\mathbb{Z}_p$ such that $\dist(w_2,y)=1$ and $\dist(v_2,y)\geq 3$, and $\dist(v_3,z)=1$ and $\dist(w_3,z)\geq 3$. Then $$(v_1,v_2,v_3)(x,v_2,z)(w_1,y,z)(w_1,w_2,w_3)$$ is a $vw$-path of length $3$. Thus $G$ has diameter at most 3. Suppose on the contrary that $G$ contains a triangle $T$. For each edge $uv$ of $T$, we have $u_i=v_i$ for exactly one value of $i\in[1,3]$. In this case, say $uv$ is \emph{type} $i$. First suppose that at least two of the edges in $T$ are the same type. Then all three edges in $T$ are the same type. Without loss of generality, $u_1=v_1=w_1$. Then the subgraph of $G$ induced by $\{u,v,w\}$ (ignoring the first coordinate) is a subgraph of the graph in \propref{TriangleFreeDiameter2}, which is triangle-free. Now assume that all three edges in $T$ have distinct types. Without loss of generality, $u_1=v_1$ and $u_2=w_2$ and $v_3=w_3$. Since $uv\in E(G)$, without loss of generality, $\dist(u_2,v_2)=1$ and $\dist(u_3,v_3)\geq 3$. Thus $\dist(v_2,w_2)=1$ and $\dist(u_3,w_3)\geq 3$. Since $vw\in E(G)$ and $u_1=v_1$, we have $\dist(u_1,w_1)=\dist(v_1,w_1)\geq 3$. We have shown that $\dist(u_1,w_1)\geq 3$ and $u_2=w_2$ and $\dist(u_3,w_3)\geq 3$. Thus the $uw$-vector is $(0,3,3)$, implying $uw\not\in E(G)$. This contradiction shows that $G$ is triangle-free. \end{proof} Finally, note that the graphs in \twopropref{TriangleFreeDiameter2}{TriangleFreeDiameter3} have bounded chromatic number. In \propref{TriangleFreeDiameter2}, colour each vertex $v$ by $(v_1 \bmod 2, v_2 \bmod 2)$. For each edge $vw$, we have $\dist(v_i,w_i)=1$ for some $i$. Since $p$ is even, $v_i\not\equiv w_i\pmod{2}$. Thus, this is a valid 4-colouring. In \propref{TriangleFreeDiameter3}, colouring each vertex $v$ by $(v_1 \bmod 2, v_2 \bmod 2,v_3\bmod 2)$ gives an 8-colouring. %} %end of journalarxiv \subsection*{Acknowledgement} The case $k=2$ of \thmref{Treewidth} was proved in collaboration with Bruce Reed. Thanks Bruce. %\bibliography{myBibliography,myConferences} %\bibliographystyle{myNatbibStyle} \def\soft#1{\leavevmode\setbox0=\hbox{h}\dimen7=\ht0\advance \dimen7 by-1ex\relax\if t#1\relax\rlap{\raise.6\dimen7 \hbox{\kern.3ex\char'47}}#1\relax\else\if T#1\relax \rlap{\raise.5\dimen7\hbox{\kern1.3ex\char'47}}#1\relax \else\if d#1\relax\rlap{\raise.5\dimen7\hbox{\kern.9ex \char'47}}#1\relax\else\if D#1\relax\rlap{\raise.5\dimen7 \hbox{\kern1.4ex\char'47}}#1\relax\else\if l#1\relax \rlap{\raise.5\dimen7\hbox{\kern.4ex\char'47}}#1\relax \else\if L#1\relax\rlap{\raise.5\dimen7\hbox{\kern.7ex \char'47}}#1\relax\else\message{accent \string\soft \space #1 not defined!}#1\relax\fi\fi\fi\fi\fi\fi} \begin{thebibliography}{30} \providecommand{\natexlab}[1]{#1} \providecommand{\url}[1]{\texttt{#1}} \providecommand{\urlprefix}{} \expandafter\ifx\csname urlstyle\endcsname\relax \providecommand{\doi}[1]{doi:\discretionary{}{}{}#1}\else \providecommand{\doi}{doi:\discretionary{}{}{}\begingroup \urlstyle{rm}\Url}\fi \bibitem[{Biggs(1974)}]{Biggs74} \textsc{Norman Biggs}. \newblock \emph{Algebraic graph theory}. \newblock Cambridge Tracts in Mathematics, No. 67. Cambridge University Press, London, 1974. \newblock \msn{0347649}. \bibitem[{Bodlaender(1998)}]{Bodlaender-TCS98} \textsc{Hans~L. Bodlaender}. \newblock A partial $k$-arboretum of graphs with bounded treewidth. \newblock \emph{Theoret. Comput. Sci.}, 209(1-2):1--45, 1998. \newblock \doi{10.1016/S0304-3975(97)00228-4}. \bibitem[{Canale and G{\'o}mez(2005)}]{CG05} \textsc{Eduardo~A. Canale and Jos{\'e} G{\'o}mez}. \newblock Asymptotically large {$(\Delta,D)$}-graphs. \newblock \emph{Discrete Appl. Math.}, 152(1-3):89--108, 2005. \newblock \doi{10.1016/j.dam.2005.03.008}. \newblock \msn{2174196}. \bibitem[{de~Bruijn(1946)}]{deBruijn} \textsc{Nicolaas~G. de~Bruijn}. \newblock A combinatorial problem. \newblock \emph{Nederl. Akad. Wetensch., Proc.}, 49:758--764, 1946. \newblock \msn{0018142}. \bibitem[{Delorme(1985)}]{Delorme85} \textsc{Charles Delorme}. \newblock Large bipartite graphs with given degree and diameter. \newblock \emph{J. Graph Theory}, 9(3):325--334, 1985. \newblock \doi{10.1002/jgt.3190090304}. \newblock \msn{812399}. \bibitem[{Demaine et~al.(0405)Demaine, Fomin, Hajiaghayi, and Thilikos}]{DH-SJDM04} \textsc{Erik~D. Demaine, Fedor~V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios~M. Thilikos}. \newblock Bidimensional parameters and local treewidth. \newblock \emph{SIAM J. Discrete Math.}, 18(3):501--511, 2004/05. \newblock \doi{10.1137/S0895480103433410}. \newblock \msn{2134412}. \bibitem[{Demaine and Hajiaghayi(2004{\natexlab{a}})}]{DH-Algo04} \textsc{Erik~D. Demaine and Mohammad Taghi Hajiaghayi}. \newblock Diameter and treewidth in minor-closed graph families, revisited. \newblock \emph{Algorithmica}, 40(3):211--215, 2004{\natexlab{a}}. \newblock \doi{10.1007/s00453-004-1106-1}. \newblock \msn{2080518}. \bibitem[{Demaine and Hajiaghayi(2004{\natexlab{b}})}]{DH-SODA04} \textsc{Erik~D. Demaine and Mohammad Taghi Hajiaghayi}. \newblock Equivalence of local treewidth and linear local treewidth and its algorithmic applications. \newblock In \emph{Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '04)}, pp. 840--849. SIAM, 2004{\natexlab{b}}. \newblock \urlprefix\url{http://dl.acm.org/citation.cfm?id=982792.982919}. \bibitem[{Diestel(2005)}]{D05} \textsc{Reinhard Diestel}. \newblock \emph{Graph theory}, vol. 173 of \emph{Graduate Texts in Mathematics}. \newblock Springer-Verlag, Berlin, 3rd edn., 2005. \newblock \urlprefix\url{http://diestel-graph-theory.com/}. \bibitem{DujMorWoo13} \textsc{Vida ~Dujmovi\'c, Pat Morin, and David R.~ Wood}. Layered separators in minor-closed families with applications. \arXiv{1306.1595}, 2014. \bibitem[{Eppstein(2000)}]{Eppstein-Algo00} \textsc{David Eppstein}. \newblock Diameter and treewidth in minor-closed graph families. \newblock \emph{Algorithmica}, 27(3-4):275--291, 2000. \newblock \doi{10.1007/s004530010020}. \newblock \msn{1759751}. \bibitem[{Fellows et~al.(1995)Fellows, Hell, and Seyffarth}]{FHS95} \textsc{Michael Fellows, Pavol Hell, and Karen Seyffarth}. \newblock Large planar graphs with given diameter and maximum degree. \newblock \emph{Discrete Appl. Math.}, 61(2):133--153, 1995. \newblock \doi{10.1016/0166-218X(94)00011-2}. \bibitem[{Fellows et~al.(1998)Fellows, Hell, and Seyffarth}]{FHS98} \textsc{Michael Fellows, Pavol Hell, and Karen Seyffarth}. \newblock Constructions of large planar networks with given degree and diameter. \newblock \emph{Networks}, 32(4):275--281, 1998. %\newblock %\doi{10.1002/(SICI)1097-0037(199812)32:4<275::AID-NET4>3.0.CO;2-G} \bibitem{FioYebAle84} \textsc{Miguel A.~ Fiol, Jos\'e L.~A. Yebra, and Ignacio Alegre}. Line digraph iterations and the $(d,k)$ digraph problem. \emph{IEEE Trans. Comput.} C-33:400--403, 1984. \newblock \doi{10.1109/TC.1984.1676455}. \bibitem[{Gavoille et~al.(2001)Gavoille, Peleg, Raspaud, and Sopena}]{GPRS01} \textsc{Cyril Gavoille, David Peleg, Andr{\'e} Raspaud, and Eric Sopena}. \newblock Small {$k$}-dominating sets in planar graphs with applications. \newblock In \emph{Graph-theoretic concepts in computer science (WG '01)}, vol. 2204 of \emph{Lecture Notes in Comput. Sci.}, pp. 201--216. Springer, 2001. \newblock \doi{10.1007/3-540-45477-2\_19}. \newblock \msn{1905633}. \bibitem[{Good(1946)}]{Good46} \textsc{Irving~J. Good}. \newblock Normal recurring decimals. \newblock \emph{J. London Math. Soc.}, 21:167--169, 1946. \newblock \doi{10.1112/jlms/s1-21.3.167}. \bibitem[{Grohe(2003)}]{Grohe-Comb03} \textsc{Martin Grohe}. \newblock Local tree-width, excluded minors, and approximation algorithms. \newblock \emph{Combinatorica}, 23(4):613--632, 2003. \newblock \doi{10.1007/s00493-003-0037-9}. \newblock \msn{2046826}. \bibitem[{Harner and Entringer(1972)}]{HE72} \textsc{Charles~C. Harner and Roger~C. Entringer}. \newblock Arc colorings of digraphs. \newblock \emph{J. Combinatorial Theory Ser. B}, 13:219--225, 1972. \newblock \doi{10.1016/0095-8956(72)90057-3}. \newblock \msn{0313101}. \bibitem[{Hell and Seyffarth(1993)}]{HS93} \textsc{Pavol Hell and Karen Seyffarth}. \newblock Largest planar graphs of diameter two and fixed maximum degree. \newblock \emph{Discrete Math.}, 111(1-3):313--322, 1993. \newblock \doi{10.1016/0012-365X(93)90166-Q}. \bibitem[{Kawai and Shibata(2002)}]{KS02} \textsc{Hiroyuki Kawai and Yukio Shibata}. \newblock The chromatic number and the chromatic index of de {Bruijn} and {Kautz} digraphs. \newblock \emph{IEICE Trans Fundam Electron Commun Comput Sci}, E85-A(6):1352--1358, 2002. \newblock \urlprefix\url{http://sciencelinks.jp/j-east/article/200215/000020021502A0487232.php}. \bibitem[{Kostochka(1982)}]{Kostochka82} \textsc{Alexandr~V. Kostochka}. \newblock The minimum {H}adwiger number for graphs with a given mean degree of vertices. \newblock \emph{Metody Diskret. Analiz.}, 38:37--58, 1982. \newblock \MSN{0713722}{}, \Zbl{0544.05037}. \bibitem[{Miller and {\v{S}}ir{\'a}{\v{n}}(2005)}]{MS-EJC05} \textsc{Mirka Miller and Jozef {\v{S}}ir{\'a}{\v{n}}}. \newblock Moore graphs and beyond: {A} survey of the degree/diameter problem. \newblock \emph{Electron. J. Combin.}, DS14, 2013. \newblock \url{http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS14}. \bibitem[{Mohar and Thomassen(2001)}]{MoharThom} \textsc{Bojan Mohar and Carsten Thomassen}. \newblock \emph{Graphs on surfaces}. \newblock Johns Hopkins University Press, Baltimore, U.S.A., 2001. \bibitem[{Nash-Williams(1964)}]{NW-JLMS64} \textsc{Crispin St. J.~A. Nash-Williams}. \newblock Decomposition of finite graphs into forests. \newblock \emph{J. London Math. Soc.}, 39:12, 1964. \newblock \doi{10.1112/jlms/s1-39.1.12}. \bibitem[{Nevo et~al.(2013)Nevo, Pineda-Villavicencio, and Wood}]{NPW} \textsc{Eran Nevo, Guillermo Pineda-Villavicencio, and David~R. Wood}. \newblock On the maximum order of graphs embedded in surfaces. \newblock \arXiv{1312.1753}, 2013. \bibitem[{Reed(1997)}]{Reed97} \textsc{Bruce~A. Reed}. \newblock Tree width and tangles: a new connectivity measure and some applications. \newblock In \emph{Surveys in combinatorics}, vol. 241 of \emph{London Math. Soc. Lecture Note Ser.}, pp. 87--162. Cambridge Univ. Press, 1997. \newblock \doi{10.1017/CBO9780511662119.006}. \bibitem[{{\v{S}}iagiov{\'a} and Simanjuntak(2004)}]{SS04} \textsc{Jana {\v{S}}iagiov{\'a} and Rinovia Simanjuntak}. \newblock A note on a {M}oore bound for graphs embedded in surfaces. \newblock \emph{Acta Math. Univ. Comenian. (N.S.)}, 73(1):115--117, 2004. \newblock % \urlprefix\url{http://www.iam.fmph.uniba.sk/amuc/_vol-73/_no_1/_siagiova/siagiova.html}. \newblock \msn{2076049}. \bibitem[{Thomason(1984)}]{Thomason84} \textsc{Andrew Thomason}. \newblock An extremal function for contractions of graphs. \newblock \emph{Math. Proc. Cambridge Philos. Soc.}, 95(2):261--265, 1984. \newblock \doi{10.1017/S0305004100061521}. \newblock \MSN{0735367}{}, \Zbl{0551.05047}. \bibitem[{Thomason(2001)}]{Thomason01} \textsc{Andrew Thomason}. \newblock The extremal function for complete minors. \newblock \emph{J. Combin. Theory Ser. B}, 81(2):318--338, 2001. \newblock \doi{10.1006/jctb.2000.2013}. \newblock \MSN{1814910}{2002i:05100}, \Zbl{1024.05083}. \bibitem[{Tishchenko(2012{\natexlab{a}})}]{Tis12} \textsc{Serge~A. Tishchenko}. \newblock Maximum size of a planar graph with given degree and even diameter. \newblock \emph{European J. Combin.}, 33(3):380--396, 2012{\natexlab{a}}. \newblock \doi{10.1016/j.ejc.2011.09.005}. \bibitem[{Tishchenko(2012{\natexlab{b}})}]{Tis12a} \textsc{Serge~A. Tishchenko}. \newblock {$N$}-separators in planar graphs. \newblock \emph{European J. Combin.}, 33(3):397--407, 2012{\natexlab{b}}. \newblock \doi{10.1016/j.ejc.2011.09.003}. \bibitem[{Zhang and Lin(1987)}]{ZL87} \textsc{Fu~Ji Zhang and Guo~Ning Lin}. \newblock On the de {B}ruijn-{G}ood graphs. \newblock \emph{Acta Math. Sinica}, 30(2):195--205, 1987. \newblock \msn{891925}. \end{thebibliography} \end{document} \appendix \begin{theorem} \label{genus} For all $\epsilon>0$ there is a constant $c$, such that for every surface $\Sigma$ of Euler genus $g$, for all $\Delta\geq\sqrt{cg+1}$ and for all odd $k\geq 3$, $$N(\Delta,k,\Sigma)\geq (1-\epsilon)\sqrt{\tfrac{3}{2}g}\,\Delta^{\floor{k/2}}\enspace.$$ \end{theorem} \begin{proof} Let $T(\Delta,\Delta',\ell)$ be the rooted tree such that the root vertex has degree $\Delta'$, every non-root non-leaf vertex has degree $\Delta$, and the distance between the root and each leaf equals $\ell$. Let $H(\Delta,\Delta',\ell)$ be the \emph{double tree} graph obtained from two copies of $T(\Delta,\Delta',\ell)$ by bijectively identifying the leaves in the two copies, as shown in Figure~\ref{DoubleTree}. We say $H(\Delta,\Delta',\ell)$ is rooted at the roots of the two copies of $T(\Delta,\Delta',\ell)$. Let $p:=\floor{(7+\sqrt{24g+1})/2}$. If $\Sigma$ is not the Klein bottle, then Ringel's map colour theorem \citep{Ringel74} implies that $K_p$ embeds in $\Sigma$. If $\Sigma$ is the Klein bottle ($g=2$) then $K_6$ embeds in $\Sigma$; let $p:=6$. Let $M$ be a maximum matching in $K_{p}$. In both cases, $|M|\geq\floor{\frac{p}{2}}\geq\sqrt{\frac{3}{2}g}$. Let $\ell:=\frac{k-1}{2}$. Let $G$ be the graph obtained by replacing each edge $vw\in M$ by a copy of $H:=H(\Delta,\Delta-p+2,\ell)$ rooted at $v$ and $w$. Clearly $G$ has diameter $k$ and maximum degree $\Delta$. Each copy of $H$ contributes at least $(\Delta-p+2)(\Delta-1)^{\ell-1}\geq(1-\epsilon)(\Delta-1)^\ell$ vertices (since $\Delta\geq\sqrt{cg+1}$ implies $\Delta-p+2\geq(1-\epsilon)(\Delta-1)$). Hence $|V(G)|\geq (1-\epsilon)|M| (\Delta-1)^\ell \geq (1-\epsilon)\sqrt{\tfrac32 g}\,(\Delta-1)^\ell$. The desired lower bound follows. \end{proof} \end{document}