Graphs with Asymptotically Invariant Degree Sequences under Restriction

Abstract

Scaling-free graphs are often used to describe a class of graphs that have the self-similarity property. The degree sequences of many scaling-free graphs follow the power-law distribution. In this paper,we study the distributions of graphical degree sequences that are invariant under “scaling.” We show that the invariant degree sequence must be a power-law distribution for sparse graphs if we ignore isolated vertices,or more generally,the vertices of degree less than a fixed constant k. We obtain a concentration result on the degree sequence of a random induced subgraph. The case of hypergraphs (or set systems) is also examined.

Acknowledgments.

Linyuan Lu's research was supported in part by NSF grant DMS 0701111.