Complete Bipartite Graphs as Induced Subgraphs of an Influence Digraph of a Time-Stamped Graph

摘要

A Time-Stamped Graph is a graph with multiple edges but no loops, where each edge is labeled with a timestamp. A timestamp is used to represent the time of a collaboration between vertices joined by the edge. Given a time-stamped graph H, the associated influence digraph of H is the digraph of the vertex set of H with an arc from Q to R iff there is a path from Q to R in H with non-decreasing timestamps. We say that Q influences R. One question that can be asked is: Given a graph G, what is the smallest time-stamped graph H so that G is an induced subgraph of the associated influence digraph of H? In this paper we show that if H is such a graph for a K_(m,m) , m ≥ 2, H has 4m vertices.