Spanning trees with few branch vertices

Louis DeBiasio; Allan Lo

doi:10.1137/17M1152759

Spanning trees with few branch vertices

Louis DeBiasio, Allan Lo

Mathematics

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

1 Citation (Scopus)

140 Downloads (Pure)

Abstract

A branch vertex in a tree is a vertex of degree at least three. We prove that, for all s ≥ 1, every connected graph on n vertices with minimum degree at least ((1/(s+3)) + o(1))n contains a spanning tree having at most s branch vertices. Asymptotically, this is best possible and solves, in less general form, a problem of Flandrin, Kaiser, Kužel, Li and Ryjáček, which was originally motivated by an optimization problem in the design of optical networks.

Original language	English
Pages (from-to)	1503–1520
Number of pages	18
Journal	SIAM Journal on Discrete Mathematics
Volume	33
Issue number	3
DOIs	https://doi.org/10.1137/17M1152759
Publication status	Published - 22 Aug 2019

Bibliographical note

19 pages

Keywords

absorbing
cs.DM
math.CO
optical networks
regularity
robust subgraphs
spanning trees

Access to Document

10.1137/17M1152759Licence: None: All rights reserved

DeBiasio_&_Lo_Spanning_Trees_with_Few_Branch_Vertices_SIAM_2019
DeBiasio, L & Lo, A 2019, 'Spanning trees with few branch vertices', SIAM Journal on Discrete Mathematics, vol. 33, no. 3, pp. 1503–1520. Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. https://doi.org/10.1137/17M1152759.
Final published version, 414 KBLicence: Other (please specify with Rights Statement)

https://epubs.siam.org/doi/abs/10.1137/17M1152759Licence: None: All rights reserved

A graph theoretical approach for combinatorial designs
Lo, A.
Engineering & Physical Science Research Council
1/11/16 → 31/10/18
Project: Research Councils

Cite this

@article{2f34bbacd81e42f18cfbdc38c56914aa,

title = "Spanning trees with few branch vertices",

abstract = "A branch vertex in a tree is a vertex of degree at least three. We prove that, for all s ≥ 1, every connected graph on n vertices with minimum degree at least ((1/(s+3)) + o(1))n contains a spanning tree having at most s branch vertices. Asymptotically, this is best possible and solves, in less general form, a problem of Flandrin, Kaiser, Ku{\v z}el, Li and Ryj{\'a}{\v c}ek, which was originally motivated by an optimization problem in the design of optical networks. ",

keywords = "absorbing, cs.DM, math.CO, optical networks, regularity, robust subgraphs, spanning trees",

author = "Louis DeBiasio and Allan Lo",

note = "19 pages",

year = "2019",

month = aug,

day = "22",

doi = "10.1137/17M1152759",

language = "English",

volume = "33",

pages = "1503–1520",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - Spanning trees with few branch vertices

AU - DeBiasio, Louis

AU - Lo, Allan

N1 - 19 pages

PY - 2019/8/22

Y1 - 2019/8/22

N2 - A branch vertex in a tree is a vertex of degree at least three. We prove that, for all s ≥ 1, every connected graph on n vertices with minimum degree at least ((1/(s+3)) + o(1))n contains a spanning tree having at most s branch vertices. Asymptotically, this is best possible and solves, in less general form, a problem of Flandrin, Kaiser, Kužel, Li and Ryjáček, which was originally motivated by an optimization problem in the design of optical networks.

AB - A branch vertex in a tree is a vertex of degree at least three. We prove that, for all s ≥ 1, every connected graph on n vertices with minimum degree at least ((1/(s+3)) + o(1))n contains a spanning tree having at most s branch vertices. Asymptotically, this is best possible and solves, in less general form, a problem of Flandrin, Kaiser, Kužel, Li and Ryjáček, which was originally motivated by an optimization problem in the design of optical networks.

KW - absorbing

KW - cs.DM

KW - math.CO

KW - optical networks

KW - regularity

KW - robust subgraphs

KW - spanning trees

UR - http://www.scopus.com/inward/record.url?scp=85071493224&partnerID=8YFLogxK

U2 - 10.1137/17M1152759

DO - 10.1137/17M1152759

M3 - Article

SN - 0895-4801

VL - 33

SP - 1503

EP - 1520

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -

Spanning trees with few branch vertices

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Projects

A graph theoretical approach for combinatorial designs

Cite this