Small universal graphs
Michael Capalbo, S. Rao Kosaraju · 1999
Let 3& be the family of N-vertex graphs of maximum degree q, and with a 2-sector function j(z) < z"'.For every constant positive 6, we show via an explicit construction algorithm that there exists an 3iT3(-universal graph r' of size O,(N).This construction is a significant improvement over the best previously known construction of size n(N2-").