𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Strongly balanced graphs and random graphs

✍ Scribed by Andrzej Ruciński; Andrew Vince

Publisher
John Wiley and Sons
Year
1986
Tongue
English
Weight
455 KB
Volume
10
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

The concept of strongly balanced graph is introduced. It is shown that there exists a strongly balanced graph with u vertices and e edges if and only if I s u -1 s e s ( 2 " ) . This result is applied to a classic question of Erdos and Renyi: What is the probability that a random graph on n vertices contains a given graph? A rooted version of this problem is also solved.

📜 SIMILAR VOLUMES

Domination-balanced graphs
Domination-balanced graphs
✍ Charles Payan; Nguyen Huy Xuong 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 355 KB

## Abstract A set __D__ of vertices in a graph is said to be a dominating set if every vertex not in __D__ is adjacent to some vertex in __D.__ The domination number β(__G__) of a graph __G__ is the size of a smallest dominating set. __G__ is called domination balanced if its vertex set can be part

Random trees and random graphs
Random trees and random graphs
✍ Tomasz Łuczak 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 205 KB 👁 2 views

In the paper we study the asymptotic behavior of the number of trees with n Ž . Ž . vertices and diameter k s k n , where n y k rnª a as n ª ϱ for some constant a-1. We use this result to determine the limit distribution of the diameter of the random graph Ž .

Balanced graphs and network flows
Balanced graphs and network flows
✍ Penrice, Stephen G. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 64 KB

A graph G is balanced if the maximum ratio of edges to vertices, taken over all subgraphs of G, occurs at G itself. This note uses the max-flow/min-cut theorem to prove a good characterization of balanced graphs. This characterization is then applied to some results on how balanced graphs may be com

Random interval graphs
Random interval graphs
✍ Nicholas Pippenger 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB 👁 1 views

We consider models for random interval graphs that are based on stochastic service systems, with vertices corresponding to customers and edges corresponding to pairs of customers that are in the system simultaneously. The number N of vertices in a connected component thus corresponds to the number o