Open AccessThe size of a maximum subgraph of the random graph with a given number of edges
Author(s) -
N. M. Derevyanko,
Н М Деревянко,
Maksim Zhukovskii,
Maksim Zhukovskii,
Michael Th. Rassias,
Michael Th. Rassias,
Arkadiy Skorkin,
А Ю Скоркин
Publication year - 2019
Publication title -
doklady akademii nauk. rossijskaâ akademiâ nauk
Language(s) - English
Resource type - Journals
ISSN - 0869-5652
DOI - 10.31857/s0869-56524886587-589
Subject(s) - mathematics , combinatorics , random graph , induced subgraph isomorphism problem , graph , graph factorization , binomial (polynomial) , random regular graph , discrete mathematics , statistics , line graph , graph power , voltage graph , pathwidth
We have proven that the maximum size k of an induced subgraph of the binomial random graph G(n, p) with a given number of edges e(k) (under certain conditions on this function), with asymptotical probability 1, has at most two values.