Random Structures & Algorithms

Diameter of P.A. Random Graphs with Edge-Steps Functions – 2019

with C. Alves (U. Leipzig) and R. Sanchis (UFMG) – Random Structures & Algorithms

Abstract

In this work we investigate a preferential attachment model whose parameter is a function f:N→[0,1] that drives the asymptotic proportion between the numbers of vertices and edges of the graph. We investigate topological features of the graphs, proving general bounds for the diameter and the clique number. Our results regarding the diameter are sharp when f is a regularly varying function at infinity with strictly negative index of regular variation −γ. For this particular class, we prove a characterization for the diameter that depends only on −γ. More specifically, we prove that the diameter of such graphs is of order 1/γ with high probability, although its vertex set order goes to infinity polynomially. Sharp results for the diameter for a wide class of slowly varying functions are also obtained.

Links

You may find the PDF file at

ArXiv

Random Structures and Algorithms

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: