Introduction

Graph models find wide application in many areas of mathematics, computer science, and the natural and social sciences. Often these models need to incorporate more structure than simply the adjacencies between vertices. In this paper we study a model that has not yet been much explored, in which each edge is associated with a point in time. Such graphs arise in modeling social structure and communication, as well as in distributed computing.

Consider, for example, the research collaboration (multi)graph $C$, in which the vertices are mathematicians (or other researchers), and there is an undirected edge joining two mathematicians for each joint paper they have published, with or without other coauthors. (See [1] for more information on $C$.) Thus, for instance, there are 20 edges between Paul Erdos and Ernst Straus, based on their numerous collaborations from 1953 to 1983; and there are three edges joining Straus and Albert Einstein--Mathematical Reviews [3] shows these joint articles in the mid-1940s. There is no edge, however, between Erdos and Einstein. If we make the simplifying assumption that the interaction between researchers takes place instantaneously, say at the moment a paper is finished, then we can assign a time-stamp to each edge. From this we see that Einstein may have influenced the thinking of Erdos, since Straus already bore the former's imprint when he worked with the latter, but not conversely. Therefore, if we construct the associated influence digraph $C^{\rm I}$ on the same vertex set as $C$, then we would find arcs from Einstein, Straus, and Erdos to each of the others except for the arc $($Erdos$,$Einstein$)$. Of course, it is possible that Erdos influenced Einstein through some longer time-increasing string of collaborations, but we know of none. Our goal here is to raise many questions about time-stamped graphs and their associated influence digraphs, and to answer a few of them.

One aspect of this problem has a long history, under terms such as gossiping and broadcasting. As originally posed and solved by numerous authors in the early 1970s, the gossip problem asks for the minimum number of telephone calls necessary and sufficient before $n$ people, each possessing a unique piece of information, can all know all the information. (The application to sharing data among remote processors is obvious.) In our setting this is asking for the minimum number of edges in a time-stamped graph on $n$ vertices whose associated influence digraph is complete, that is, contains all $n(n-1)$ possible arcs. The answer turns out to be $2n-4$ for all $n \ge 4$. A survey paper in 1988 [2] lists 135 references on this and related questions. In these investigations, however, the emphasis has been on the dissemination of information, rather than on the influences among the vertices.

In this paper, graph will mean an undirected multigraph (parallel edges, but not loops, are allowed), and digraph will mean a directed graph without loops or (except in Section 6) parallel arcs (in the same direction). It will often be convenient to regard a simple graph (one with no parallel edges) as a digraph by replacing each edge by a pair of arcs joining its two endpoints in opposite directions. As is customary, we let $E(G)$ (respectively, $A(D)$) denote the set of edges of a graph $G$ (respectively, arcs of a digraph $D$).

A time-stamped graph $G=(V,E)$ is a graph together with a function $c:E\longrightarrow{\mathbb{R}}$, called the time-stamp function. We will use the ordered pair $(G,c)$ to denote the graph $G$ with the time-stamp function $c$. Let $e_1,e_2,\ldots,e_t$ be the edge-sequence of a path in $G$. It is a non-decreasing path if $c(e_1)\leq c(e_2)\leq \cdots\leq c(e_t)$. Let $u$ and $v$ be distinct vertices of $V$. We say that $u$ influences $v$ if there is a non-decreasing path from $u$ to $v$. Construct the associated influence digraph $G^{\rm I}_c$ (or $G^{\rm I}$, if $c$ is clear from the context) as follows: Its vertex set is $V$, and $(u,v)$ is an arc if $u$ influences $v$. Moreover, if $u$ influences $v$ and $v$ influences $u$, then we can use an undirected edge instead of two arcs in opposite directions. We think of the arcs of $G^{\rm I}_c$ as the influences induced (or generated) by the non-decreasing paths in $G$.

In the collaboration graph application, a paper with more than two authors creates a clique in $C$ on the vertices corresponding to the authors, all with the same time-stamp. However, we may, in fact, always make the time-stamp function injective. Indeed, consider the subgraph of a time-stamped graph induced by the edges with the same time-stamp $t$. Successively replace the edges in each component by a clique (i.e., form the transitive closure of the subgraph) having time-stamps $t+\epsilon,t+2\epsilon,\ldots,t+k\epsilon$ where $\epsilon$ is chosen so that the interval $[t,t+k\epsilon]$ contains no other time-stamps present in the graph. It is clear that the new time-stamped graph generates the same set of influences as the original one. We note that the new time-stamped graph may not retain all the structural properties of the old graph. For example, if the original time-stamped graph is a tree, then the revised one is not.

We remark that one can construct $G^{\rm I}$ from $(G,c)$ in polynomial time. The following algorithm computes it in $O(n^3)$ time for a time-stamped graph with $n$ vertices.

1. Order the edges in increasing order with respect to the time-stamps. (As stated above, if $c$ is not injective, we may first replace $(G,c)$ by $(G',c')$ on the same vertex set with $c'$ injective.)
2. For each vertex $v$, set $I(v)=\{v\}$. The set $I(v)$ will be the set of vertices that are known to influence $v$, together with $v$ itself.
3. For each edge in the ordered list of edges, do the following:
   Let the edge be $\{u,v\}$. Replace $I(u)$ by $I(u)\cup I(v)$, and replace $I(v)$ by $I(u)\cup I(v)$.
4. For every $x,y\in V$, put the arc $(x,y)$ into $A(G^{\rm I})$ if and only if $x\in I(y)\setminus\{y\}$.

In this paper we study the realizability problem: Given a set of parameters, we ask whether there is a graph $G$ and a time-stamp function $c$ such that the associated influence digraph $G^{\rm I}_c$ has certain prescribed values of the given parameters. If not, can we find a graph $G$ and a(n injective) time-stamp function $c$ such that the associated influence digraph has values for this set of parameters that are ``closest'' to the prescribed values? On the one hand, a very restricted form of this question is to use a digraph as the parameter; that is, is there a graph $G$ and a time-stamp function $c$ such that $G^{\rm I}_c$ is the given digraph? If the given digraph is the complete graph, then the answer is obviously yes. Finding a way to do this with as few edges as possible is the gossip problem discussed above. On the other hand, a relaxed form of this question is to use the number of vertices and the number of arcs as the parameters. In this paper we give a solution to this relaxed question:

Problem 1.1   Let $t$ and $n$ be positive integers. Is there a graph in some class $\mathcal C$ of graphs with $n$ vertices and an injective time-stamp function such that the associated influence digraph has $n$ vertices and $t$ arcs?

We note that the explicit requirement that $c$ is injective has substance. Although we have already observed that for any pair $(G,c)$, there is another pair $(H,c')$ with $c'$ injective such that the associated influence digraphs of $G$ and $H$ are the same, $H$ does not necessarily belong to $\mathcal C$. We restrict $c$ to be injective for the following reason: Since a class $\mathcal C$ is selected, we do not want to implicitly step out of $\mathcal C$ by using a non-injective function.

In Section 2 we solve Problem 1.1 when $\mathcal C$ is the set of trees and then extend it to the case when $\mathcal C$ is the set of forests. Moreover, we show that every realizable value for trees can be achieved by a tree homeomorphic to $K_2$ or $K_{1,3}$. Those trees that give rise to the maximum realizable value and the minimum realizable value are also classified. In Section 3 we solve Problem 1.1 when $\mathcal C$ is unrestricted and when $\mathcal C$ is the set of connected graphs. In Section 4 we consider the most restricted problem, namely, given a digraph $D=(V,A)$, does there exist a pair $(G,c)$ such that $D=G^{\rm I}_c$? A more general problem is to find a smallest graph $H$ whose associated influence digraph has $D$ as an induced subdigraph. Let $p(D)=\vert V(H)\vert-\vert V(D)\vert$. We will show that this function in well-defined. Some upper bounds for $p$ are given in Section 5; moreover, we compute $p$ of a star and conjecture a formula for $p$ of a tree. Finally, in Section 6 we extend our study to directed interactions between vertices; we also pose some open questions.