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