CCA-2726 Original Scientific Paper Two Models for Random Graphs with Bounded Degree

Two digraphs both of whose nodes consist of the set of unlabeled graphs of order n having bounded vertex degree equal to f are stud-ied. Adjacency in these digraphs is defined via one-edge transfor-mations of the node graphs. Probabilities on the arcs are intro-duced so that one digraph is a strictly evolving absorbing Markov chain and the other an ergodic Markov chain. Probabilistic and de-terministic results and problems concerning these Markov chains are presented. An example of physical interest in these chains is in models where the nodes of the digraphs are identified with chemi-cal species. Key words: random graph, Markov chain, bounded degree. 1