#### Title

Induced Paths in the Influence Digraph of a Time-Stamped Graph

#### Document Type

Article

#### Publication Date

2006

#### Publication Source

Congressus Numerantium

#### Volume

181

#### Inclusive pages

195-215

#### Peer Reviewed

yes

#### Abstract

A time-stamped graph is an extension of the concept of a collaboration graph which accounts for the relative timing of collaborations. Edges, corresponding to specific acts of collaboration, are labeled with time-stamps. In a time-stamped graph H, vertex Q influences vertex R iff there is a non-decreasing path from Q to R in H. Given a time-stamped graph H, the associated influence digraph of H is the digraph on the vertex set of H with an arc from Q to R iff Q influences R in H. One question that can be asked: Given a graph G, what is the smallest number of vertices that must be added to the vertex set of G so that G is an induced subdigraph of the associated influence digraph of some time-stamped graph H on that expanded vertex set? Cheng, Grossman, and Lipman conjectured that for trees with n vertices the answer to this question is n-2. In this paper the conjecture is verified for paths.

#### Keywords

time-stamped graphs, induced subgraphs, influence digraphs

#### Disciplines

Discrete Mathematics and Combinatorics | Mathematics

#### Opus Citation

Marc Lipman (2006).
Induced Paths in the Influence Digraph of a Time-Stamped Graph. *Congressus Numerantium*.181, 195-215.

http://opus.ipfw.edu/math_facpubs/113