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

Improve this question
$\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
    Commented Feb 3, 2011 at 20:13

4 Answers 4

Reset to default
35
$\begingroup$

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

Improve this answer
$\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$
    – Bill Bradley
    Commented 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.

Improve this answer
$\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$
    – Derrick Stolee
    Commented 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)$.

Improve this answer
$\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$
    – Suresh Venkat
    Commented 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$
    – David Eppstein
    Commented Feb 3, 2011 at 23:19
0
$\begingroup$

see representation number of graph by ring

it is useful.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .