Bounds for $p$

In this section we give some upper bounds for $p$. We start with the following simple bound.

Proposition 5.1   Let $D$ be a digraph with $m$ arcs. Then $p(D)\leq m$.

Proof. Let $n$ be the number of vertices of $D$. We construct $H$ as follows. Replace each arc $e_i=(u,v)$ in $D$ by two undirected edges, $\{u,y_i\}$ with time-stamp $i$ and $\{y_i,v\}$ with time-stamp $m+i$, where $y_i$ is a new vertex. Then $H$ has $m+n$ vertices and all time-stamps are distinct. It is easy to see that $D$ is the subdigraph of $H^{\rm I}_c$ induced by the vertices of $D$. Hence $p(D)\leq m$. $\qedsymbol$

For trees, we can improve this bound. We consider an undirected tree $T$ with $n$ vertices as a digraph. For the tree with two vertices in Figure 5a, Figure 5b gives a time-stamped graph whose associated influence digraph contains Figure 5a as an induced subgraph. Although it is not optimal, it provides a basic structure to use in an arbitrary tree. We call the graph in Figure 5b a tadpole, with $u$ its head and $v$ its tail. The edge incident to $v$, called the tail-edge, has a medium time-stamp, whereas the edges incident to $u$ have a small time-stamp and a large time-stamp.

Figure 5: A tree with two vertices and a time-stamped graph

To apply this idea to an arbitrary tree, we root the tree at some vertex. We now carry out the procedure described in Figure 5, replacing each edge by a tadpole, with an adjustment so that there are no repeated time-stamps, working from the top down to guarantee that no two tails coincide (see Figure 6 and Figure 7). It is easy to check that the resulting graph is a time-stamped graph whose associated influence digraph contains $T$ as an induced subdigraph. This gives the following result.

Proposition 5.2   Let $T$ be a tree with $n$ vertices. Then $p(T)\leq n-1$.

Figure 6: A rooted tree

Figure 7: A time-stamped graph with seven new vertices whose associated influence digraph contains Figure 6 as an induced subdigraph

This is better than the bound given in Proposition 5.1. However, this bound is not optimal (even for trees), since $p(K_2)=0<1$. To improve this bound, we note that in our construction, we just have to avoid two tails coinciding. Every vertex is a tail except the root. So we will not apply the procedure at one of the edges incident to the root; this edge, called a special edge, will have a medium time-stamp (see Figure 8). Thus we have

Theorem 5.3   Let $T$ be a tree with $n$ vertices. Then $p(T)\leq n-2$.

This is optimal for a tree with two vertices. Can we do better in general? We note that our construction is not unique. Consider a path on four vertices. Figure 9 gives two additional constructions. Consider a star of size 3. Figure 10 gives a different construction. As we will prove next, this bound is optimal for stars. We conjecture that it is optimal for trees.

Figure 8: A time-stamped graph with six new vertices whose associated influence digraph contains Figure 6 as an induced subdigraph

Figure 9: Both the second and the third graph are time-stamped graphs whose associated influence digraph has the first graph as an induced subdigraph. Both are different from the construction given in the proof of Theorem 5.3.

Figure 10: The second graph is a time-stamped graph whose associated influence digraph has the first graph as an induced subdigraph. The construction is different from the construction given in the proof of Theorem 5.3.

Theorem 5.4   Let $T=K_{1,n-1}$ be a star with $n$ vertices. Then $p(T)=n-2$.

Proof. This follows directly from Theorem 5.3 and Proposition 4.6. $\qedsymbol$

Conjecture 5.5   Let $T$ be a tree with $n$ vertices. Then $p(T)=n-2$.

We can now give a better bound on $p$ for graphs, based on the bound for trees.

Proposition 5.6   Let $D=(V,A)$ be a digraph with $n$ vertices and $m$ arcs. Let $E$ be the set of edges of $D$, i.e., the pairs of vertices joined by antiparallel arcs. Suppose $(V,E)$ is a connected graph. Then $p(D)\leq m-n$.

Proof. Let $T$ be a spanning tree of $(V,E)$. We apply the procedure given in the proof of Theorem 5.3 to obtain a time-stamped graph whose associated influence digraph is the subdigraph of $D$ induced by $T$. Moreover, we choose the time-stamps on the tail-edges of all the tadpoles to be 4, the time-stamps on the two edges of each tadpole incident to its head to be 1 and 6 respectively, and the time-stamp on the special edge to be 3. Let $A'$ be $A$ with all the arcs forming the edges in $T$ removed. For every arc in $A'$, we apply the procedure given in the proof of Proposition 5.1 with the additional constraint that one of the two time-stamps generated by such an arc is 2 while the other is 5. It is routine to check that the subgraph induced by $V$ of the digraph associated with this time-stamped graph is $D$. Every arc generated one new vertex, with the exception that every edge (two arcs) in $T$ other than the special edge generated only one new vertex and the special edge (two arcs) generated none. This gives a saving of $(n-2)+2$ new vertices, so $p(G)\leq m-(n-2)-2=m-n$, as required. $\qedsymbol$

Another way of looking at Proposition 5.6 is that we have a special edge that doesn't generate any new vertices, and we have trees rooted at vertices of this special edge, whose edges generate one vertex for each edge (two arcs) rather than two. We can use any clique in place of this special edge, leading to the following result.

Theorem 5.7   Let $D=(V,A)$ be a digraph with $n$ vertices and $m$ arcs. Let $E$ be the set of edges of $D$, i.e., the pairs of vertices joined by antiparallel arcs. Suppose $(V,E)$ is a connected graph with a clique of size $k$. Then $p(D)\leq m-n-k^2+2k$.

Proof. Let $\mathcal K$ be a clique of size $k$ with vertices $v_1,v_2,\ldots,v_k$ in $(V,E)$. Let $T_1,T_2,\ldots,T_k$ be the trees in a spanning forest of $(V,E)\setminus E(\mathcal K)$ rooted at $v_1,v_2,\ldots,v_k$ respectively. It is clear that such a spanning forest exists. We apply the procedure given in the proof of Proposition 5.2 (not Theorem 5.3) to obtain a time-stamped graph $G_i$ for each $T_i$ such that the subdigraph of $G^{\rm I}_i$ induced by $V(T_i)$ is $T_i$. Moreover, we choose the time-stamps on the tail-edges of all the tadpoles to be 4, and the time-stamps on the two edges of each tadpole incident to its head to be 1 and 6 respectively. Each edge in $\mathcal K$ is given time-stamp 3. Let $A'$ be the set of arcs not in $E(\mathcal K)\dot\cup E(T_1)\dot\cup E(T_2)\dot\cup\cdots\dot\cup E(T_k)$. For every arc in $A'$, we apply the procedure given in the proof of Proposition 5.1, but with the two time-stamps generated by such an arc being 2 and 5. It is routine to check that the subdigraph induced by $V$ of the digraph associated with this time-stamped graph is $D$. Since every arc generated one new vertex with the exception that every edge (two arcs) in $T_i$ generated only one new vertex and every edge (two arcs) in $\mathcal K$ generated none, we have a saving of $(n-k)+2{k \choose 2}$ vertices, so $p(D)\leq m-(n-k)-2{k \choose 2}=m-n-k^2+2k$, as required. $\qedsymbol$

A remark similar to Remark 4.9 can be made to the construction given in the proof of Proposition 5.6 and Theorem 5.7. In fact, Theorem 5.7 can be strengthened with only a slight modification. We state this generalization without proof.

Theorem 5.8   Let $D=(V,A)$ be a digraph with $n$ vertices and $m$ arcs. Let $E$ be the set of edges of $D$, i.e., the pairs of vertices joined by antiparallel arcs. Suppose $(V,E)$ is a connected graph with vertex-disjoint cliques of sizes $k_1,k_2,\ldots,k_r$. Then

$$p(D)\leq m-n-\sum_{i=1}^r(k_i^2-2k_i).$$