Abstract:

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