A note on universal graphs for spanning trees

Ervin Győri; Binlong Li; Nika Salia; Casey Tompkins

doi:10.1016/j.dam.2024.11.008

A note on universal graphs for spanning trees

Ervin Győri
, Binlong Li
, Nika Salia^*
, Casey Tompkins

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

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

Original language	English
Pages (from-to)	146-147
Number of pages	2
Journal	Discrete Applied Mathematics
Volume	362
DOIs	https://doi.org/10.1016/j.dam.2024.11.008
State	Published - 15 Feb 2025

Bibliographical note

Publisher Copyright:
© 2024 Elsevier B.V.

Keywords

Extremal number
Spanning trees
Trees
Universal graphs

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2024.11.008

Cite this

@article{7398b3843f394287ab568c180fabda8b,

title = "A note on universal graphs for spanning trees",

abstract = "Chung and Graham considered the problem of minimizing the number of edges in an n-vertex graph containing all n-vertex trees as a subgraph. They showed that such a graph has at least [Formula presented] edges. In this note, we improve this lower estimate to nlogn−O(n).",

keywords = "Extremal number, Spanning trees, Trees, Universal graphs",

author = "Ervin Gy{\H o}ri and Binlong Li and Nika Salia and Casey Tompkins",

note = "Publisher Copyright: {\textcopyright} 2024 Elsevier B.V.",

year = "2025",

month = feb,

day = "15",

doi = "10.1016/j.dam.2024.11.008",

language = "English",

volume = "362",

pages = "146--147",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - A note on universal graphs for spanning trees

AU - Győri, Ervin

AU - Li, Binlong

AU - Salia, Nika

AU - Tompkins, Casey

PY - 2025/2/15

Y1 - 2025/2/15

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

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

KW - Extremal number

KW - Spanning trees

KW - Trees

KW - Universal graphs

UR - https://www.scopus.com/pages/publications/85209939403

U2 - 10.1016/j.dam.2024.11.008

DO - 10.1016/j.dam.2024.11.008

M3 - Article

AN - SCOPUS:85209939403

SN - 0166-218X

VL - 362

SP - 146

EP - 147

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

A note on universal graphs for spanning trees

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this