×

Bounded expansion in web graphs. (English) Zbl 1212.05248

Summary: 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 an unbounded expansion, too.

MSC:

05C83 Graph minors
94C15 Applications of graph theory to circuits and networks
90B10 Deterministic network models in operations research
90B15 Stochastic network models in operations research
PDFBibTeX XMLCite
Full Text: EuDML EMIS