What is the number of $n$-vertex [median graphs](https://en.wikipedia.org/wiki/Median_graph)? 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](http://www.fmf.uni-lj.si/~klavzar/preprints/MESHED.pdf))


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](http://dx.doi.org/10.1137/S0895480197323494) ([preprint](http://www.fmf.uni-lj.si/~klavzar/preprints/IKM-REV1.pdf))


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](https://oeis.org/A006785), [A024607](https://oeis.org/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$.]



Number of median graphs?
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.)


