Dirk Schlatter
Bounded expansion in web graphs

Comment.Math.Univ.Carolinae 50,2 (2009) 181-190.

Abstract:In this paper we study various models for web graphs with respect to bounded expansion. All the deterministic models even have constant expansion, whereas the copying model has unbounded expansion. The most interesting case turns out to be the preferential attachment model --- which we conjecture to have unbounded expansion, too.

Keywords: graph minors, bounded expansion, webgraphs
AMS Subject Classification: 05C83 94C15 90B10 90B15

PDF