On a method for random graphs

Zbigniew Palka; Andrzej Rucinśki; Joel Spencer

doi:10.1016/0012-365X(86)90096-8

On a method for random graphs

Zbigniew Palka, Andrzej Rucinśki, Joel Spencer

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper we examine a method for establishing an almost sure existence of a subgraph of a random graph with a given subgraph property. Since the method has been abused in the literature, we state some conditions under which it can be safely used. As an illustration we apply the method to induced cycles, maximal induced trees and arbitrary subgraphs of a random graph K_n,p.

Original language	English (US)
Pages (from-to)	253-258
Number of pages	6
Journal	Discrete Mathematics
Volume	61
Issue number	2-3
DOIs	https://doi.org/10.1016/0012-365X(86)90096-8
State	Published - Sep 1986

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(86)90096-8

Cite this

@article{ebdd5bd8cb1443ca903a98fda215f817,

title = "On a method for random graphs",

abstract = "In this paper we examine a method for establishing an almost sure existence of a subgraph of a random graph with a given subgraph property. Since the method has been abused in the literature, we state some conditions under which it can be safely used. As an illustration we apply the method to induced cycles, maximal induced trees and arbitrary subgraphs of a random graph Kn,p.",

author = "Zbigniew Palka and Andrzej Rucin{\'s}ki and Joel Spencer",

year = "1986",

month = sep,

doi = "10.1016/0012-365X(86)90096-8",

language = "English (US)",

volume = "61",

pages = "253--258",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "2-3",

}

TY - JOUR

T1 - On a method for random graphs

AU - Palka, Zbigniew

AU - Rucinśki, Andrzej

AU - Spencer, Joel

PY - 1986/9

Y1 - 1986/9

N2 - In this paper we examine a method for establishing an almost sure existence of a subgraph of a random graph with a given subgraph property. Since the method has been abused in the literature, we state some conditions under which it can be safely used. As an illustration we apply the method to induced cycles, maximal induced trees and arbitrary subgraphs of a random graph Kn,p.

AB - In this paper we examine a method for establishing an almost sure existence of a subgraph of a random graph with a given subgraph property. Since the method has been abused in the literature, we state some conditions under which it can be safely used. As an illustration we apply the method to induced cycles, maximal induced trees and arbitrary subgraphs of a random graph Kn,p.

UR - http://www.scopus.com/inward/record.url?scp=46149128674&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=46149128674&partnerID=8YFLogxK

U2 - 10.1016/0012-365X(86)90096-8

DO - 10.1016/0012-365X(86)90096-8

M3 - Article

AN - SCOPUS:46149128674

SN - 0012-365X

VL - 61

SP - 253

EP - 258

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2-3

ER -

On a method for random graphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this