Fragile minor-monotone parameters under random edge perturbation

D.Y. Kang; M. Kang; J. Kim; S.-I. Oum

Fragile minor-monotone parameters under random edge perturbation

D.Y. Kang, M. Kang, J. Kim, S.-I. Oum

Institute of Discrete Mathematics (5050)

Research output: Working paper › Preprint

Abstract

We investigate how minor-monotone graph parameters change if we add a few random edges to a connected graph H. Surprisingly, after adding a few random edges, its treewidth, treedepth, genus, and the size of a largest complete minor become very large regardless of the shape of H. Our results are close to best possible for various cases. Copyright © 2020, The Authors. All rights reserved

Original language	English
Publication status	Published - 2020

Access to Document

https://arxiv.org/abs/2005.09897

Cite this

@techreport{141d068af5714750809c5ba12bf6dfa8,

title = "Fragile minor-monotone parameters under random edge perturbation",

abstract = "We investigate how minor-monotone graph parameters change if we add a few random edges to a connected graph H. Surprisingly, after adding a few random edges, its treewidth, treedepth, genus, and the size of a largest complete minor become very large regardless of the shape of H. Our results are close to best possible for various cases. Copyright {\textcopyright} 2020, The Authors. All rights reserved",

author = "D.Y. Kang and M. Kang and J. Kim and S.-I. Oum",

year = "2020",

language = "English",

type = "WorkingPaper",

}

TY - UNPB

T1 - Fragile minor-monotone parameters under random edge perturbation

AU - Kang, D.Y.

AU - Kang, M.

AU - Kim, J.

AU - Oum, S.-I.

PY - 2020

Y1 - 2020

N2 - We investigate how minor-monotone graph parameters change if we add a few random edges to a connected graph H. Surprisingly, after adding a few random edges, its treewidth, treedepth, genus, and the size of a largest complete minor become very large regardless of the shape of H. Our results are close to best possible for various cases. Copyright © 2020, The Authors. All rights reserved

AB - We investigate how minor-monotone graph parameters change if we add a few random edges to a connected graph H. Surprisingly, after adding a few random edges, its treewidth, treedepth, genus, and the size of a largest complete minor become very large regardless of the shape of H. Our results are close to best possible for various cases. Copyright © 2020, The Authors. All rights reserved

UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-85095317498&partnerID=MN8TOARS

M3 - Preprint

BT - Fragile minor-monotone parameters under random edge perturbation

ER -

Fragile minor-monotone parameters under random edge perturbation

Abstract

Access to Document

Other files and links

Fingerprint

Cite this