pith. sign in

arxiv: 0706.1642 · v1 · submitted 2007-06-12 · 💻 cs.DM · math.CO

On the growth of components with non fixed excesses

classification 💻 cs.DM math.CO
keywords componentverticesexpectedgraphnumbertendsaddingbelong
0
0 comments X
read the original abstract

Denote by an $l$-component a connected graph with $l$ edges more than vertices. We prove that the expected number of creations of $(l+1)$-component, by means of adding a new edge to an $l$-component in a randomly growing graph with $n$ vertices, tends to 1 as $l,n$ tends to $\infty$ but with $l = o(n^{1/4})$. We also show, under the same conditions on $l$ and $n$, that the expected number of vertices that ever belong to an $l$-component is $\sim (12l)^{1/3} n^{2/3}$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.