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 Hon 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.
展开▼
