next up previous
Next: Introduction


A time-stamped graph is an undirected graph with a real number on each edge. Vertex $ u$ influences vertex $ v$ if there is a non-decreasing path from $ u$ to $ v$. The associated influence digraph of a time-stamped graph is the directed graph that records the influences. Among other results, we determine for what $ n$ and $ t$ there exists a time-stamped graph whose associated influence digraph has $ n$ vertices and $ t$ 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

Time-Stamped Graphs and Their Associated Influence Digraphs

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

Date: May 1, 2003

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

Eddie Cheng 2003-05-01