#### Title

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

#### Document Type

Article

#### Publication Date

2006

#### Publication Source

Congressus Numerantium

#### Volume

181

#### Inclusive pages

65 - 76

#### Peer Reviewed

yes

#### Abstract

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.

#### Keywords

influcence digraphs, induced subgraphs, cycle

#### Disciplines

Discrete Mathematics and Combinatorics | Mathematics

#### Opus Citation

Marc Lipman (2006).
Induced Cycles in the Influence Digraph of a Time-Stamped Graph. *Congressus Numerantium*.181, 65 - 76.

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