Vertex Labeling and Routing in Recursive Clique-Trees, a New Family of Small-World Scale-Free Graphs

摘要

We present a new category of graphs, recursive clique-trees K(q,t) (with q≥2 and t ≥ 0), which have small-world and scale-free properties and allow a fine tuning of the clustering and the power-law exponent of their discrete degree distribution. This family of graphs is a generalization of recent constructions with fixed degree distributions. We first compute the relevant characteristics of those graphs: diameter, clustering and power law exponent. Then we propose a labeling of the vertices of K(q,t), for any q ≥ 2 and t ≥ 0, that allows to determine a shortest path routing between any two vertices of K(q,t), only based on the above mentioned labels.