
Let \(G_{1/2}(n)\) denote a random graph with \(n\) vertices in which each pair is selected to be an edge independently with probability \(1/2\). Almost all of them satisfy several basic properties which turn out to be equivalent. Families of graphs satisfying this equivalence class of properties are called quasi-random, see e.g. \textit{F. R. K. Chung}, \textit{R. L. Graham} and \textit{R. M. Wilson} [Combinatorica 9, 345--362 (1989; Zbl 0715.05057)]. So far most of the results dealt with dense quasi-random graphs (having \(cn^2\) edges for some \(c>0\) as \(n \rightarrow \infty\)). This article studies quasi-random graphs with \(o(n^2)\) edges for analogous results, which are more difficult, due for example to the possible absence of certain local structures, such as 4-cycles.
Random graphs (graph-theoretic aspects), random graphs
Random graphs (graph-theoretic aspects), random graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 34 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
