Dense subgraphs of power-law random graphs

The problem of finding a maximal dense subgraph of a power-law random graph $G (n, α)$ is considered for every value of density $c \in (0, 1)$ and for every $α \in (0, + \infty)$ . It is shown that in case $α < 2$ a maximal $c$ -dense subgraph has size $Θ_{p} (n^{1 - α ∕ 2})$ , in case $α = 2$ it is limited whp, and in case $α > 2$ it is whp less than $\frac{4}{c}$ .

PDF Access Denied

We have not been able to recognize your IP address 18.224.149.242 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 40.00:

Keywords

power-law random graph, Poissonian model, maximal dense subgraph, graph density, maximal dense subgraph of random graph.

Mathematical Subject Classification 2010

Primary: 05C42

Secondary: 05C69

Milestones

Received: 27 December 2019

Revised: 21 July 2020

Accepted: 7 August 2020

Published: 16 January 2021

Authors

Denis O. Lazarev
Theoretical Computer Science Departement Ivannikov Institute for System Programming of the RAS Moscow Russia

Nikolay N. Kuzyurin
Theoretical Computer Science Departement Ivannikov Institute for System Programming of the RAS Moscow Russia

Vol. 10, No. 1, 2021

Denis O. Lazarev and Nikolay N. Kuzyurin

Abstract

PDF Access Denied

Keywords

Mathematical Subject Classification 2010

Milestones

Authors