**November 29, 2000 from
1:30 - 3:25 in K9509, SFU
**

**
**

**Prabhakar Raghavan, Verity Corporation
From 1:30 - 2:20 Talks on
**

**"Networks and Sub-Networks in the World-Wide Web"
**

** 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.

Romeo Rizzi

Instituto Trentino di Cultura, IRST, Trento, Italy

email: rizzi@itc.it

From 2:35 - 3:25 Talks on

**"Indecomposable $r$-graphs and some other counterexamples"
**

** 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.