Induced Cycles in the Influence Digraph of a Time-Stamped Graph
65 - 76
A time-stamped graph is a graph with multiple edges but no loops, where each edge is labeled with a time-stamp. A time-stamp is intended to represent the time of collaboration between the vertices joined by the edge. Given a time-stamped graph H, the assiciated influence digraph of H is the digraph on the vertex set of H with an arc from Q to R iff there is a path from Q to R in H which has non-decreasing time-stamps. We then say that Q influences R. One question that can be asked: Given a graph G, what is the smallest number of vertices in some time-stamped graph H so that G is realized as an induced subdigraph of the associated influence digraph of H.In this paper we show that if H is such a graph for a cycle on n vertices, greater than or equal to 4, then H has 2n vertices.
influcence digraphs, induced subgraphs, cycle
Discrete Mathematics and Combinatorics | Mathematics
Marc Lipman (2006).
Induced Cycles in the Influence Digraph of a Time-Stamped Graph. Congressus Numerantium.181, 65 - 76.