The problem of finding a maximal dense subgraph of a power-law random graph
is considered for
every value of density
and for every
. It is
shown that in case
a maximal
-dense
subgraph has size
,
in case
it is limited
whp, and in case
it
is whp less than
.
Keywords
power-law random graph, Poissonian model, maximal dense
subgraph, graph density, maximal dense subgraph of random
graph.