Graphs

We now turn our attention to Problem 1.1 when $\mathcal C$ is unrestricted and when $\mathcal C$ is the set of connected graphs. In this section whether or not the time-stamp function $c$ is injective is moot, because of the observation in Section 1. Since $t_{\min}(m)=3m-1$, a connected time-stamped graph with $m+1$ vertices cannot generate fewer than $3m-1$ influences, and clearly $m(m+1)$ is the maximum possible number of influences. Our next result shows that every value in this range can be achieved.

Theorem 3.1   For every integer $t$ in $[3m-1,m(m+1)]$, there exists $(G,c)$ where $G$ is a connected graph with $m+1$ vertices such that $G^{\rm I}_c$ has $t$ arcs.

Proof. We know that the range $[3m-1,m(m+3)/2]$ can be obtained from trees. Thus we only need to consider the range $[m(m+3)/2+1,m(m+1)]$. Now $m(m+3)/2$ influences can be obtained from a path with vertices $\{v_1,v_2,\ldots,v_{m+1}\}$ and edges between $v_i$ and $v_{i+1}$ with time-stamp $i$ for $i=1,2,\ldots,m$. Adding an edge between $v_i$ and $v_j$ with time-stamp $i$ where $j\geq i+2$ gives $j-i-1$ additional influences, namely, the influences from $j$ to $b$ for $b=i,i+1,\ldots,j-2$. Let $S(j)$ be the number of additional influences from $j$ to $b$ with $b<j$ given by this construction. Then $S(j)$ is a unique element in $\{0,1,2,\ldots,j-2\}$. (The number 0 corresponds to not adding any edge.) It is easy to see that the additional influences involving $j_1$ and $j_2$ using this construction are different if $j_1\neq j_2$. Hence by picking an element from each of $S(3),S(4),\ldots,S(m+1)$, we can add $q$ additional influences for any $q\leq m(m-1)/2$, bringing the total up to any value not exceeding $m(m+3)/2+m(m-1)/2=m(m+1)$. $\qedsymbol$

The next corollary extends the result to the unrestricted case.

Corollary 3.2   Let $\mathcal F$ be $\emptyset$ if $m=1$, $\{3,4\}$ if $m=2$, $\{3,7\}$ if $m=3$, and $\{3\}$ if $m\geq 4$. Then there exists $(G,c)$ where $G$ is a nontrivial graph (not necessarily connected) with $m+1$ vertices such that $G^{\rm I}_c$ has $t$ arcs if and only if $t\in[2,m(m+1)]\setminus\mathcal F$.

Proof. We note that $t=3$ is not realizable. The result for $m=1$ and $m\geq 5$ follows from Theorem 2.5, Corollary 2.6, and Theorem 3.1. It is also easy to check the cases for $m=2,3,4$. $\qedsymbol$