Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider graphs on $n$ nodes. I am trying to find a graph $G$ that contains all $n$-node trees as sub-graphs but contains as few edges as possible. The complete graph $K_n$ suffices, but can we get by with fewer edges? Maybe $O(n)$ edges?

(This problem arose in the context of circuit design, where edges in $G$ correspond to wires in a chip layout.)

share|improve this question
2  
Great question! I read it and thought, "This looks like something Bill would be interested in. Oh wait..." –  Noah Stein Feb 3 '11 at 20:13

4 Answers 4

up vote 30 down vote accepted

See Chung and Graham, On Universal Graphs for Spanning Trees. They prove that the number of edges is $\Theta(n\log n)$.

share|improve this answer
    
Thanks! That's perfect. They also explictly construct such a graph in the paper. For the record, the reference is from J. London Math. Soc. (2), 27 (1983), pp 203-211. –  Bill Bradley Feb 5 '11 at 17:41

Well, $O(n)$ will not do, as you need 1 vertex of degree $n-1$, a total of two vertices of degree $\ge \frac{n}{2}$, etc., to embedd all the trees with few vertices of high degree and only leaves otherwise. That should get you $cn\log n$ edges as a lower bound.

My guess is that this should be about right asymptotically, as you should be able to take a random graph with average degree $c\Delta\log n$ to get (all?) trees of max degree $\Delta$ (see http://arxiv.org/abs/1007.2326), and add some large degree vertices to get all other trees from this.

share|improve this answer
    
Some care must be taken here: the star on $n-1$ vertices has maximum degree $n-1$. A tree given by an edge with each endpoint adjacent to $\frac{n-2}{2}$ vertices has two vertices of maximum degree $\frac{n-1}{2}$. For $k \geq 3$, the tree with a $k$-degree vertex whose neighbors are adjacent to $\frac{n-(k+1)}{k}$ other vertices has $k$ vertices of maximum degree $\frac{n-1}{k}$. Following your technique, the $k$ vertices of degree at least $\frac{n-1}{k}$ could be the first $k$ of the $k+1$ vertices of degree at least $\frac{n-1}{k+1}$, but one is missing. This gives $nH_n = cn\log n$ edges. –  Derrick Stolee Feb 3 '11 at 19:43

The standard term is "universal graphs", I think. See http://en.wikipedia.org/wiki/Universal_graph According to that entry the answer is indeed $O(n \log n)$.

share|improve this answer
    
Isn't the n log n bound there for bounded degree planar graphs ? For polytrees it seems a little less, however it might not be possible to capture any given tree as an induced subgraph of a polytree. –  Suresh Venkat Feb 3 '11 at 15:36
    
This answer is correct that the standard term is universal graphs, but the Wikipedia article doesn't seem to have the information about trees in it. Maybe someone should add it... –  David Eppstein Feb 3 '11 at 23:19

see representation number of graph by ring

it is useful.

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.