Graph theory random graphs

PalE85 Palmer, E. M. Graphical Evolution. An introduction to the theory of random graphs. Wiley-Iiherscience Series in Discrete Mathematics, John Wiley and Sons, 1985. 

Sequences folding into the same structure form neutral networks in sequence space. A mathematical model based on random graph theory was designed [16] in order to allow for the derivation of analytical expressions. Neutral networks are represented by graphs in sequence space that show an interesting percolation phenomenon depending on the... 

To discover new fitness peaks, the neutral network must be sufficiently extended, allowing neutral drift to effectively sample sequence space. A neutral network can be characterized by a mean fraction of neutral neighbors A (Reidys et al., 1997). If A exceeds a threshold A,., then the network is connected and dense, making it more likely the network percolates through sequence space. If A < Ac, the networks are partitioned into components. Using random graph theory, the threshold is derived analytically as... 

D.J. Klein, J.L. Palacios, M. Randic, and N. Trinajstic, Random walks and chemical graph theory, J. Chem. Irf. Comput. ScL 44 (2004) 1521-1525. 

M. Requardt, Spectral analysis and operator theory on (infinite) graphs..JPA (in press) math-ph/0001026 M. Requardt (Quantum) space-time as a statistical geometry of lumps in random networks, Class. Quant. Grav. 17, 2029 (2000) gr-qc/9912059. 

---