Recent Issues
Volume 13, Issue 4
Volume 13, Issue 3
Volume 13, Issue 2
Volume 13, Issue 1
Volume 12, Issue 4
Volume 12, Issue 3
Volume 12, Issue 2
Volume 12, Issue 1
Volume 11, Issue 4
Volume 11, Issue 3
Volume 11, Issue 2
Volume 11, Issue 1
Volume 10, Issue 4
Volume 10, Issue 3
Volume 10, Issue 2
Volume 10, Issue 1
Volume 9, Issue 4
Volume 9, Issue 3
Volume 9, Issue 2
Volume 9, Issue 1
Volume 8, Issue 4
Volume 8, Issue 3
Volume 8, Issue 2
Volume 8, Issue 1
Older Issues
Volume 7, Issue 4
Volume 7, Issue 3
Volume 7, Issue 2
Volume 7, Issue 1
Volume 6, Issue 4
Volume 6, Issue 2-3
Volume 6, Issue 1
Volume 5, Issue 4
Volume 5, Issue 3
Volume 5, Issue 1-2
Volume 4, Issue 4
Volume 4, Issue 3
Volume 4, Issue 2
Volume 4, Issue 1
Volume 3, Issue 3-4
Volume 3, Issue 2
Volume 3, Issue 1
Volume 2, Issue 4
Volume 2, Issue 3
Volume 2, Issue 2
Volume 2, Issue 1
Volume 1, Issue 4
Volume 1, Issue 3
Volume 1, Issue 2
Volume 1, Issue 1
Abstract
The problem of finding a maximal dense subgraph of a power-law random graph
G ( n , α ) is considered for
every value of density
c
∈ ( 0 , 1 )
and for every
α
∈ ( 0 , + ∞ ) . 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
4
c .
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