The size of the largest hole in a random graph
type: Item
instance of: scholarly article
title: The size of the largest hole in a random graph
zbMATH Open document ID: 0779.05050
DOI: 10.1016/0012-365X(93)90230-Q
author: Tomasz Łuczak
published in: Discrete Mathematics
publication date: 1993-08-30T00:00:00Z
review text: It is shown that almost every random graph with the expected average degree \(c\), where \(c\) is a constant larger than one, contains an induced cycle which goes through a positive fraction of the vertices of the graph. Furthermore, for large \(c\), the length of the longest induced cycle is determined up to a factor of two. A similar result was proved independently by \textit{Stephen W. C. Suen} [J. Comb. Theory, Ser. B 56, No. 2, 250-262 (1992; see the review below)].
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 179595
zbMATH Keywords: largest hole
zbMATH Keywords: random graph
zbMATH Keywords: induced cycle
MaRDI profile type: Publication
cites work: The number of matchings in random regular graphs and bipartite graphs
cites work: Trees in random graphs
cites work: Q3286850
cites work: Induced trees in sparse random graphs
cites work: Large holes in sparse random graphs
cites work: Large induced trees in sparse random graphs
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Q4726290
cites work: Maximal induces trees in sparse random graphs
cites work: The chromatic number of random graphs at the double-jump threshold
cites work: Q3816113
Recommended article: The largest hole in sparse random graphs
Recommended article: Large holes in quasi-random graphs
Recommended article: Holes in random graphs
Recommended article: Large holes in sparse random graphs
Recommended article: The coverage holes of the largest component of random geometric graph
Recommended article: On the size of a random maximal graph
Recommended article: Size of the giant component in a random geometric graph
Recommended article: The Size of the Giant Component of a Random Graph with a Given Degree Sequence
description: scientific article; zbMATH DE number 179595