Premium
Strongly balanced graphs and random graphs
Author(s) -
Ruciński Andrzej,
Vince Andrew
Publication year - 1986
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190100214
Subject(s) - combinatorics , mathematics , random regular graph , random graph , discrete mathematics , graph , line graph , pathwidth
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 ⩽( ν 2 ). 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.