On the distribution in a graph process

DOI10.1016/0012-365X(84)90057-8MaRDI QIDQ795841zbMATH OpenFDO

Publication date 1984

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(84)90057-8

Factorials, binomial coefficients, combinatorial functions (05A10) Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80)

Review text

A graph \(G_{n+1}\) is obtained from a graph \(G_ n\) by adding a new point with probability \(p_ n\) and inserting a new line at random with probability \(1-p_ n\) for \(n=1,2,...\). Here \(p_ n=1\) if \(G_ n\) is complete, and \(p_ n=p\) otherwise. The initial graph \(G_ 1\) consists of a simple point. Various properties of the graph process were investigated by \textit{M. Capobianco} and \textit{O. Frank} [Discrete Math. 46, 133-143 (1983; Zbl 0513.05049)] using lattice path methods. This note shows how determinantal lattice path counting formulas can be applied in this context.

Recommendations

Cited in

(10)

This page was built for publication: On the distribution in a graph process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q795841)