35
$\begingroup$

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.)

$\endgroup$
1
  • 2
    $\begingroup$ Great question! I read it and thought, "This looks like something Bill would be interested in. Oh wait..." $\endgroup$
    – Noah Stein
    Feb 3, 2011 at 20:13

4 Answers 4

35
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Feb 5, 2011 at 17:41
17
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Feb 3, 2011 at 19:43
7
$\begingroup$

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)$.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Feb 3, 2011 at 15:36
  • $\begingroup$ 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... $\endgroup$ Feb 3, 2011 at 23:19
0
$\begingroup$

see representation number of graph by ring

it is useful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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