Portal de Periódicos da CAPES

Strongly balanced graphs and random graphs

1986; Wiley; Volume: 10; Issue: 2 Linguagem: Inglês

10.1002/jgt.3190100214

1097-0118

Andrzej Ruciński, Andrew Vince,

Stochastic processes and statistical mechanics

Abstract The concept of strongly balanced graph is introduced. It is shown that there exists a strongly balanced graph with v vertices and e edges if and only if I ν – 1 ⩽ e ⩽( ). This result is applied to a classic question of Erdös and Rényi: What is the probability that a random graph on n vertices contains a given graph? A rooted version of this problem is also solved.