Abstract: We discuss several structural properties of graphs arising from the world-wide web including the graph of hyperlinks, and the graph induced by connections between distributed search servents. We review a number of algorithmic investigations of the structure of these networks, and conclude by proposing stochastic models for the evolution of these networks.

Abstract:An $r$-graph is any graph that can be obtained as a conic combination of its own $1$-factors. Equivalenty, an $r$-graph is an $r$-regular graph such that at least $r$-edges leave each odd-cardinality subset of nodes. An $r$-graph $(V,E)$ is indecomposable if its edge set $E$ cannot be partitioned as $E=E_1 \cup E_2$ so that $(V,E_1)$ and $(V,E_2)$ are both $r$-graphs. We construct an indecomposable $r$-graph for every integer $r\geq 4$. This answers a question posed by Seymour and implies that the coefficients in the Schrijver System (minimal TDI system) of the $T$-cut polyhedron are not bounded by any constant.

A graph in which every two $1$-factors intersect is said to be poorly matchable. Every poorly matchable $r$-graph is indecomposable. We show that the converse of this statement is false for $r\geq 4$. Further, we construct a poorly matchable $r$-graph for every $r\geq 4$.

Related topics: Fulkerson Coloring Conjecture, Seymour's Coloring Conjecture, Hilbert bases, packing $T$-joins, colorings and flows.