On the tree-depth and tree-width in heterogeneous random graphs

Research output: Contribution to journalArticlepeer-review

Abstract

In this note, we investigate the tree-depth and tree-width in a heterogeneous random graph obtained by including each edge eij (i≠j) of a complete graph Kn over n vertices independently with probability pn(eij). When the sequence of edge probabilities satisfies some density assumptions, we show both tree-depth and tree-width are of linear size with high probability. Moreover, we extend the method to random weighted graphs with non-identical edge weights and capture the conditions under which with high probability the weighted tree-depth is bounded by a constant.
Original languageEnglish
Pages (from-to)78-83
Number of pages6
JournalProceedings of the Japan Academy Series A: Mathematical Sciences
Volume98
Issue number9
Early online date11 Nov 2022
DOIs
Publication statusPublished - 11 Nov 2022

Fingerprint

Dive into the research topics of 'On the tree-depth and tree-width in heterogeneous random graphs'. Together they form a unique fingerprint.

Cite this