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

Shang, Yilun (2022) On the tree-depth and tree-width in heterogeneous random graphs. Proceedings of the Japan Academy, Series A, Mathematical Sciences, 98 (9). pp. 78-83. ISSN 0386-2194

treetree.pdf - Accepted Version

Download (153kB) | Preview
Official URL: https://doi.org/10.3792/pjaa.98.015


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.

Item Type: Article
Uncontrolled Keywords: heterogeneous graph, random graph, tree-depth, tree-width
Subjects: G100 Mathematics
Department: Faculties > Engineering and Environment > Computer and Information Sciences
Depositing User: John Coen
Date Deposited: 15 Nov 2022 12:14
Last Modified: 15 Nov 2022 12:39
URI: https://nrl.northumbria.ac.uk/id/eprint/50657

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics