33
$\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$
  • 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 '11 at 20:13
34
$\begingroup$

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

$\endgroup$
  • $\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$ – Bill Bradley Feb 5 '11 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$
  • $\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$ – Derrick Stolee Feb 3 '11 at 19:43
6
$\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$
  • $\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$ – Suresh Venkat Feb 3 '11 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$ – David Eppstein Feb 3 '11 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, privacy policy and cookie policy

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