A time-stamped graph is an undirected graph
with a real number on each edge. Vertex influences vertex
if there is a non-decreasing path from to . The associated influence
digraph of a time-stamped graph is the directed graph that
records the influences.
Among other results, we determine for what and there exists a
time-stamped graph whose
associated influence digraph has vertices and arcs.
We also investigate the minimum number of vertices a graph can have so that a
given digraph is an induced subgraph of its associated influence digraph.
A number of other questions are also explored.

**AMS Subject Classification:** primary: 05C38; secondary: 05C35, 90B10,
91D30, 94C15

**Keywords:** time-stamped graph, influence, collaboration, Erdos
number

**Eddie Cheng, Jerrold W. Grossman, and Marc J. Lipman**

*Date:* May 1, 2003

Department of Mathematics and Statistics, Oakland University, Rochester, Michigan USA 48309

- Introduction
- Trees
- Graphs
- The Restricted Question
- Bounds for
- Concluding Remarks
- Bibliography
- About this document ...

Eddie Cheng 2003-05-01