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

This document is currently not available here.

  Contact Author

Share

COinS