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