A note on universal graphs for spanning trees

Győri, Ervin and Li, Binlong and Salia, Nika and Tompkins, Casey (2025) A note on universal graphs for spanning trees. DISCRETE APPLIED MATHEMATICS, 362. pp. 146-147. ISSN 0166-218X

Preview	Text 2311.01488v2.pdf - Draft Version Download (64kB) | Preview
	Text 1-s2.0-S0166218X24004803-main.pdf - Published Version Restricted to Repository staff only Download (332kB) | Request a copy

Abstract

Chung and Graham considered the problem of minimizing the number of edges in an nvertex graph containing all n-vertex trees as a subgraph. They showed that such a graph has at least 1 2 n log n edges. In this note, we improve this lower estimate to n log n−O(n).

Actions (login required)

Edit Item