7
$\begingroup$

What is the number of $n$-vertex median graphs? These graphs generalize hypercubes and trees, and have many applications. It seems unlikely that a closed form expression is known, so I would also be interested in asymptotics or lower bounds. For more about median graphs see the survey by Klavžar and Mulder:

  • Sandi Klavžar, Henry Martyn Mulder, Median graphs: characterizations, location theory and related structures, J. Combin. Math. Combin. 30 (1999) 103–127. (preprint)

Imrich et al. claimed to have shown (at least "intuitively") that there are as many median graphs as there are triangle-free graphs. Their argument involves composing a sequence of injections. Since the sets involved are infinite, this is unfortunately not rigorous enough to conclude anything about the actual numbers.

  • Wilfried Imrich, Sandi Klavžar, Henry Martyn Mulder, Median graphs and triangle-free graphs, SIAM J. Discrete Math. 12 (1999) 111–118. doi:10.1137/S0895480197323494 (preprint)

Given the apparent connection with triangle-free graphs, I would also be interested in asymptotics or bounds for the number of $n$-vertex triangle-free graphs, for which OEIS has the following relevant sequences: A006785, A024607.

[In an effort to make the question more self-contained, I append the definition of median graph from the Wikipedia link: In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices $a$, $b$, and $c$ have a unique median: a vertex $m(a,b,c)$ that belongs to shortest paths between each pair of $a$, $b$, and $c$.]

$\endgroup$
6
$\begingroup$

The numbers of $m$-edge triangle-free and median graphs are of similar types — at least, the logarithms of these numbers are within a constant factor of each other. In one direction every median graph is triangle-free, and in the other direction the simplex graph of an $m$-edge triangle-free graph is median and has $O(m)$ edges.

However, for $n$-vertex graphs, the triangle-free and median graphs have very different numbers. A median graph, or more generally a partial cube, can be completely described by giving a spanning tree together with a partition of the edges of the spanning tree into equivalence classes for the Djokovic equivalence relation, so the number of median graphs is at most exponential in $n\log n$, because it takes $O(n)$ bits to specify a tree and $O(n\log n)$ bits to specify a partition of the edges. On the other hand, the number of triangle-free graphs, or even the number of subgraphs of $K_{n/2,n/2}$, is exponential in $\Theta(n^2)$.

I'm not sure whether the number of $n$-vertex median graphs is exponential in $n$, $n\log n$, or something in between, but my intuition is $n$. (There's an easy lower bound that is exponential in $n$: every tree is a median graph.)

$\endgroup$
  • $\begingroup$ Thanks for the bounds, just what I was looking for! Do you know if these arguments appear in work (published more formally than here) that I could cite? $\endgroup$ – András Salamon Nov 24 '14 at 10:12
  • $\begingroup$ Not that I know of, no. $\endgroup$ – David Eppstein Nov 24 '14 at 16:37

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.