Induced Paths in the Influence Digraph of a Time-Stamped Graph
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.
time-stamped graphs, induced subgraphs, influence digraphs
Discrete Mathematics and Combinatorics | Mathematics
Marc Lipman (2006).
Induced Paths in the Influence Digraph of a Time-Stamped Graph. Congressus Numerantium.181, 195-215.