The Size of a Maximum Subgraph of the Random Graph with a Given Number of Edges


Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

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 asymptotic probability 1, has at most two values.

About the authors

N. M. Derevyanko

Moscow Institute of Physics and Technology (National Research University)

Email: zhukmax@gmail.com
Russian Federation, Dolgoprudnyi, Moscow oblast, 141700

M. E. Zhukovskii

Moscow Institute of Physics and Technology (National Research University); Caucasus Mathematical Center; Russian Presidential Academy of National Economy
and Public Administration

Author for correspondence.
Email: zhukmax@gmail.com
Russian Federation, Dolgoprudnyi, Moscow oblast, 141700; Maykop, Republic of Adygea, 385000; Moscow, 119571

M. Rassias

University of Zurich

Email: zhukmax@gmail.com
Switzerland, Zurich

A. Yu. Skorkin

Adyghe State University

Email: zhukmax@gmail.com
Russian Federation, Maykop, Republic of Adygea, 385000

Supplementary files

Supplementary Files
Action
1. JATS XML

Copyright (c) 2019 Pleiades Publishing, Ltd.