Title

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

Document Type

Article

Publication Date

2006

Publication Source

Congressus Numerantium

Volume

181

Inclusive pages

195-215

Peer Reviewed

yes

Abstract

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.

Keywords

time-stamped graphs, induced subgraphs, influence digraphs

Disciplines

Discrete Mathematics and Combinatorics | Mathematics

This document is currently not available here.

  Contact Author

Share

COinS