Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

thanks for letting me become a member.

I have a rather basic question on graph theory. Suppose G is a finite graph, without loops, multiple edges or directed edges. Let n be the number of vertices, let $\Delta$ be the maximum degree.

Find an upper bound on the number of edges in the graph. (Note that I am not assuming anything about the diameter).

Is there a symbol for this, or any literature on the web or in books? Are there any tables on the web for small n and small $\Delta$?

This could be seen as a problem in extremal graph theory, but here the forbidden subgraph is simply a star on $\Delta+2$ vertices.

A very naive upper bound is simply $n\Delta/2$, but that bound can only be attained by regular graphs, and if n and $\Delta$ are both odd, then the bound is not an integer and thus certainly not attained.

Many thanks!

share|improve this question
    
As you mention, the naive upper bound is all that can be said in general. If you want to say more, you need to introduce other parameters or make other assumptions about the graph. –  Andrew Uzzell Jan 21 '13 at 11:50
2  
I think the answer, absent further restrictions on the graph, is the greatest integer not exceeding $n\Delta/2$. –  Gerry Myerson Jan 21 '13 at 11:55
    
Thanks for the replies and for editing that tag. So there is no similar theorem yielding a somewhat better bound? Are there perhaps any results on the ratio between Delta/n. For instance, if Delta/n< 1/3 then (for large n) the number of edges is at most "..."? –  fred Jan 21 '13 at 21:08

1 Answer 1

Circulant graphs can be used to realize the $\lfloor n\Delta/2 \rfloor$ bound in a large number of cases, and in the other cases, we can modify them slightly to achieve this bound.

  • When $n$ is even and $\Delta$ is even (so $\Delta \leq n-2$), we pick a set of distances comprising $\Delta/2$ distances in $\{1,2,\ldots,n/2-1\}$.

For example, when $n=10$ and $\Delta=6$, we can take the distances $\{1,2,3\}$, which gives:

$n=10$ and $\Delta=6$ case

  • When $n$ is even and $\Delta$ is odd, we pick a set of distances comprising $(\Delta-1)/2$ distances in $\{1,2,\ldots,n/2-1\}$ and $n/2$.

For example, when $n=10$ and $\Delta=5$, we can take the distances $\{1,2,5\}$, which gives:

$n=10$ and $\Delta=5$ case

  • When $n$ is odd and $\Delta$ is even we pick a set of distances comprising $\Delta/2$ distances in $\{1,2,\ldots,(n-1)/2\}$.

For example, when $n=11$ and $\Delta=6$, we can take the distances $\{2,3,4\}$, which gives:

$n=11$ and $\Delta=6$ case

Finally, when $n$ is odd and $\Delta$ is odd (so $\Delta \leq n-2$), $n\Delta/2$ is not an integer, so we can't achieve the maximum with circulant graphs. The best we could possibly do is $\lfloor n\Delta/2 \rfloor$. To achieve this:

  • We take a $(\Delta-1)$-regular graph as above, but do not take distance $1$ edges (we need to take at most $(\Delta-1)/2 \leq (n-3)/2$ distances, so this is possible).

  • We observe that the edges of distance $1$ form a Hamilton cycle in the complement of the graph. We pick $(n-1)/2$ disjoint edges from this Hamilton cycle (i.e., no two edges share an endpoint), and add them to our construction.

For example, when $n=11$ and $\Delta=7$, we can take the above $6$-regular graph and add in edges around the outside as follows:

$n=11$ and $\Delta=7$ case

This gives $\lfloor n\Delta/2 \rfloor$ edges in every case (as expected).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.