The Restricted Question

In this section we consider the most restrictive parameter, giving us the following problem.

Problem 4.1   Let $D$ be a digraph with $n$ vertices. Is there a graph $H$ in the class $\mathcal C$ with $n$ vertices and a(n injective) time-stamp function $c$ such that $H^{\rm I}_c=D$?

We say that $D$ is realizable if the answer to Problem 4.1 is yes. For the remainder of this paper, we assume that the class $\mathcal C$ is the class of all graphs. (Hence in light of the observation in Section 1, we can allow $c$ to be non-injective in our proofs without any loss of strength.) Unlike the more relaxed Problem 1.1, the answer to Problem 4.1 is often no. For example, suppose $G\neq K_2$ is an undirected connected simple graph (i.e., viewed as a digraph, all of its arcs occur in antiparallel pairs). If there exists a vertex $v$ such that the subgraph of $G$ induced by the neighbours of $v$ is not connected or deg$(v)=1$, then $G$ is not realizable as an associated influence digraph. This will be proved below. So it is natural to consider the following definition and problem.

Definition 4.2   Given a digraph $D=(V,A)$, let

$$p(D)=\min\;\{\;\vert V(H^{\rm I}_c)\vert-\vert V(D)\vert\;:\;$$$$\mbox{$D$\ is an induced subdigraph of $H^{\rm I}_c$}$$$$\;\},$$

where the minimum is taken over all time-stamped graphs $(H,c)$.

Problem 4.3   Find $p(D)$ for a given digraph $D$.

We note that $p$ is well-defined, as we will give an upper bound for $p$ in Proposition 5.1. As an application, let $D$ be a digraph on the set of mathematicians. Then if $D$ is not the collaboration influence digraph for mathematicians, is it perhaps an induced subdigraph of the influence digraph for mathematicians and physicists?

Clearly a digraph $D$ is realizable if and only if $p(D)=0$. We now give examples in which $p(D)>0$. Although we are dealing with directed graphs, we wonder whether the special case when $D$ is generated from an undirected graph would be easier. These examples consider the general case when $D$ directed and the special case when $D$ is an undirected graph (each undirected edge representing two arcs).

Proposition 4.4   Suppose $D$ is a directed graph with at least three vertices whose underlying undirected graph² $G$ is connected³. If there exists a vertex $v$ such that $\deg_G(v)\leq 2$, then $p(D)\geq 1$.

Proof. Suppose $p(D)=0$. Let $H$ be a time-stamped graph giving rise to $D$. Then $D$ and $H$ (and hence $G$ and $H$) have the same vertex set. Clearly deg$_G(u)\geq 2$ for every vertex $u$. Suppose deg$_G(v)=2$. Note that $H$ is connected since $G$ is connected. Clearly $v$ must have degree 1 in $H$ as deg$_G(v)=2$. Now, $H$ has at least three vertices, $H$ is connected, and $v$ has degree 1. Therefore there must be a path of length 2 of the form $v,u,w$. Note that $v$ and $u$ influence each other. Now, either $v$ influences $w$ or vice versa, depending on the time-stamps on the edges $\{v,u\}$ and $\{u,w\}$. In either case, this implies deg$_G(v)\geq 3$, a contradiction. $\qedsymbol$

Corollary 4.5   Suppose $G\neq K_2$ is an undirected connected graph. If there exists a vertex $v$ such that $\deg(v)=1$, then $p(G)\geq 1$.

Proposition 4.6   Suppose $D$ is a directed graph whose underlying undirected graph $G$ is connected. If there exists a vertex $v$ such that the subgraph of $G$ induced by the neighbours of $v$ has $k\geq 2$ components, then $p(D)\geq k-1$.

Proof. Let the vertex set of $D$ be $V$. Let $H$ with vertex set $V\;\dot\cup\; W$ be a time-stamped graph such that $T=H^{\rm I}$. Let the components of the subgraph of $G$ induced by the neighbours of $v$ be $C_1,C_2,\ldots,C_k$. For $i=1,2,\ldots,k$, there is a non-decreasing path $P_i$ in $H$ between $v$ and a vertex $v_i$ in $C_i$, and we may assume that every internal vertex (if any) belongs to $W$. If $P_i$ is of length at least 2, let $w_i$ be the first internal vertex on $P_i$ from $v_i$ to $v$ in $H$. (We note that although $P_i$ may be a non-decreasing path from $v$ to $v_i$, $w_i$ will still be selected according to this rule.) Call $w_i$ the slave of $v_i$ and $v_i$ the master of $w_i$. We claim that at most one of $P_1,P_2,\ldots,P_k$ is of length 1. Suppose not, say $P_i$ and $P_j$ are of length 1. Then we have a path of length 2 from $v_i$ to $v_j$ in $H$. Hence either $v_i$ influences $v_j$ or vice versa, a contradiction to the definition of $C_i$ and $C_j$. Although $w_i$ may be an internal vertex of $P_j$, we claim that $w_i\neq w_j$, that is, no slave can serve two masters. If this is not the case, we would have a path of length 2 from $v_i$ to $v_j$ in $H$, a contradiction. Hence we have constructed $k-1$ distinct elements of $W$, as desired. $\qedsymbol$

Corollary 4.7   Suppose $G$ is an undirected connected graph. If there exists a vertex $v$ such that the subgraph of $G$ induced by the neighbours of $v$ has $k$ components, then $p(G)\geq k-1$.

Given these stringent necessary conditions, one may wonder whether there are large classes of graphs that are realizable. The next proposition gives such a class: a complete graph with the edges of a clique removed. (The graph $K_n\setminus E(K_m)$ is often described as the join of $K_{n-m}$ and an independent set of $m$ vertices, or as a complete multipartite graph with one part of size $m$ and $n-m$ parts of size 1.)

Proposition 4.8   Let $G=K_n\setminus E(K_m)$ where $n\geq 2m$. Then $p(G)=0$. In particular, $p(K_n)=0$.

Proof. Let $V_1=\{v_1,v_2,\ldots,v_m\}$, $V_2=\{v_{m+1},v_{m+2},\ldots,v_{2m}\}$, and $V_3=\{v_{2m+1},v_{2m+2},\ldots,v_n\}$. Note that $V_1$ or $V_3$ may be empty. Construct the graph $H$ with vertex set $V_1\cup V_2\cup V_3$ as follows: For all $u,v\in V_2\cup V_3$, put two edges between $u$ and $v$, where one has time-stamp 1 and the other has time-stamp 3; and put one edge between $v_i$ and $v_{m+i}$ with time-stamp 2 for all $1\leq i\leq m$. Then it is easy to check that $H^{\rm I}=K_n\setminus E(K_m)$. $\qedsymbol$

Remark 4.9   We note that the graph constructed in Proposition 4.8 will not be more complication even if we want $c$ to be injective. Instead of the general technique of computing transitive closure given in Section 1, the construction in the proof of Proposition 4.8 will work if the time-stamps are all within $1/3$ of their stated values.

Proposition 4.8 gives us a nice class of realizable graphs, but these graphs are dense. So one might think that if $p(D)=0$, then $D$ must be ``close'' to complete. This is not the case, as we already have a class of digraphs $D$ with $n$ vertices and $3n-4$ arcs having $p(D)=0$, namely, the associated influence digraphs of $(T,c)$ that achieve $t_{\min}(n-1)$; see Theorem 2.1. For an undirected example, let $G$ be the graph whose vertices are $\{0,1,2,\ldots,2k-1\}$ where $2k\geq 6$ with undirected edges from $i$ to $i\pm 1$ and $i\pm 2$, as well as from $2i$ to $2i-3$ for all $i$ (everything modulo $2k$). Then $G=H^{\rm I}$ where $V(H)=V(G)$ and $H$ has an edge with time-stamp approximately 2 between $2i$ and $2i+1$, an edge with time-stamp approximately 1 between $2i$ and $2i-1$, and an edge with time-stamp approximately 3 between $2i$ and $2i-1$ for all $i$ (everything modulo $2k$).