3
$\begingroup$

I posted this on stackexchange but due to a lack of response there I am posting here.

Let $G$ be a graph with girth $g$, minimal degree $\delta$, maximal degree $\Delta$, and diameter $D$. Define $$n_0(g,\delta) := \begin{cases} 1 + \delta + \delta(\delta-1) + \cdots + \delta(\delta-1)^{\frac{g-3}{2}}, & \mbox{ if }g \mbox{ is odd} \\ 2+2(\delta-1)+\cdots+ 2(\delta-1)^{\frac{g}{2}-1}, & \mbox{ if } g \mbox{ is even}. \end{cases}.$$

Suppose the girth $g$ is odd. It can be shown that the number of vertices of $G$ is bounded as $n_0(g,\delta) \le |V| \le n_0(2D+1,\Delta)$. Also, $g \le 2D+1$ for any graph. Graphs that are extremal with respect to any one of these three inequalities are called Moore graphs. I say any one, because it seems like the following are equivalent:

(a) $|V|=n_0(g,\delta)$.

(b) $|V|=n_0(2D+1,\Delta)$

(c) $g=2D+1$.

My question is: if the girth of the graph is assumed to be even, then what would be the analogous bounds and definitions and the three statements that are equivalent (an upper bound on the number of vertices that is met with equality, a lower bound that is met with equality, and a relationship between diameter and girth)? I can see that to obtain a good lower bound (the one given above), we need to do a bread-first search starting from two adjacent vertices rather than a single vertex. But some things related to the upper bound are not clear to me.

For example, given that a graph $G$ has diameter $D$, maximum degree $\Delta$ and even girth $g$, what is an upper bound on the number of vertices of $G$?

In the text [Bollobas, Modern Graph Theory, p. 106 and Ex. 4.4], the even girth case is treated not by specifying the diameter, but by specifying that every vertex is within distance $d-1$ from each edge. In this case, I think the following are equivalent (please correct me if I am wrong):

(a') $|V|=n_0(2d,\Delta)$

(b') $g=2d$ and $G$ is regular.

(c') $|V|=n_0(g,\delta)$ and $g$ is even.

I guess something is not clear to me because we aren't starting off by specifying the diameter in the beginning here. It seems to me that if the equivalences hold then the diameter is equal to $d$, though that isn't explicitly stated in the text.

Perhaps another way to ask my question is: if I want to study the degree/diameter problem for graphs of even girth by first proving an upper bound (rather than lower bound) for $|V|$ (and then proceeding to study the extremal graphs of this inequality), what would the upper bound (and additional assumptions used to prove the upper bound) be?

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.