Trees

In this section we solve Problem 1.1 for trees (undirected, connected graphs with no loops, multiple edges, or cycles). In fact, we will give a solution using a restricted class of trees. Let $t$ and $m$ be positive integers. Is there a tree $T$ with $m+1$ vertices and an injective time-stamp function $c$ such that the associated influence digraph has $t$ arcs? Since a tree with $m+1$ vertices has $m$ edges, we may restrict $c$ to be a bijective function $c:E(T)\longrightarrow\{1,2,\ldots,m\}$. Let

$$t_{\max}(m)=\max\;\{\;\vert A(T^{\rm I}_c)\vert\;:\;$$$$\mbox{$T$\ is a tree with $m$\ edges, and $c$\ is a time-stamp function for $T$}$$$$\;\}$$

and

$$t_{\min}(m)=\min\;\{\;\vert A(T^{\rm I}_c)\vert\;:\;$$$$\mbox{$T$\ is a tree with $m$\ edges, and $c$\ is a time-stamp function for $T$}$$$$\;\}.$$

Theorem 2.1   Let $m\geq 1$. Then $t_{\max}(m)=m(m+3)/2$ and $t_{\min}(m)=3m-1$. If $(T,c)$ is a maximizer for $t_{\max}(m)$, then $T$ is a caterpillar¹; in addition, for every caterpillar $T$, there is a time-stamp function $c$ such that $(T,c)$ is a maximizer for $t_{\max}(m)$. If $(T,c)$ is a minimizer for $t_{\min}(m)$, then $T$ is a path.

Proof. Since each edge induces two arcs in the associated influence digraph and each path of length 2 induces at least one arc in the associated influence digraph, $\vert A(T^{\rm I}_c)\vert\geq 2m+a(T)$ where $a(T)$ is the number of paths of length 2 in $T$. We claim that

$$m-1=\min\;\{\;a(T)\;:\;$$$$\mbox{$T$\ is a tree with $m$\ edges}$$$$\;\}.$$

We first observe that the path with $m$ edges gives $m-1$ paths of length 2. We claim that this is the unique minimizer for $a(T)$. The proof is by induction, the base cases being trivial. Let $T^*$ be a minimizer for $a(T)$ with $m$ edges, and assume that $T^*$ is not a path. Then $T^*$ has a vertex $v$ of degree $k\geq 3$. Let $B_1,B_2,\ldots,B_k$ be the trees obtained by deleting $v$. Let $T_i$ be the tree obtained by deleting the vertices of $B_j$ from $T$ for all $j\neq i$; in particular $v\in V(T_i)$. By the induction hypothesis, each $T_i$ has at least $m_i-1$ paths of length 2, where $m_i$ is the number of edges in $T_i$. So $\sum_{i=1}^km_i=m$. Hence the number of paths of length 2 in $T^*$ is at least

$$\sum_{i=1}^k(m_i-1)+{k \choose 2}=m-k+{k \choose 2}>m-1.$$

Hence the path is the unique minimizer for $a(T)$ over trees with $m$ edges. This shows that $t_{\min}(m)\geq 3m-1$; and if $(T,c)$ is a minimizer that attains $t_{\min}(m)=3m-1$, then $T$ is a path. We now show that this is attainable. Let the vertex set of the path be $\{v_1,v_2,\ldots,v_{m+1}\}$ and the edge set be $\{e_1,e_2,\ldots,e_m\}$, where $e_i=\{v_i,v_{i+1}\}$. Then any bijections

$$c_{\rm odd}:\{\;e_i\;:\;$$$$\mbox{$i$\ is odd}$$$$\;\}\longrightarrow \left\{1,2,\ldots,\left\lceil\frac{k}{2}\right\rceil\right\}$$

and

$$c_{\rm even}:\{\;e_i\;:\;$$$$\mbox{$i$\ is even}$$$$\;\}\longrightarrow \left\{\left\lceil\frac{k}{2}\right\rceil+1, \left\lceil\frac{k}{2}\right\rceil+2,\ldots,k\right\}$$

will do. (See Figure 1 for $m=7$.)

Figure 1: A path

Since each edge induces two arcs in the associated influence digraph, each path of length at least 2 induces at most one arc in the associated influence digraph, and there is a unique path between two distinct vertices in a tree, $t_{\max}(m)\leq 2m+\left({m+1 \choose 2}-m\right)=m(m+3)/2$. We first observe that a star with any $c$ gives this maximum, so it is attainable. We now show that if $(T,c)$ is a maximizer, then $T$ is a caterpillar. Suppose not. Let $T$ be a tree that is not a caterpillar but has an influence one way or the other between every pair of vertices. Since $T$ is not a caterpillar, it has a subgraph that is a subdivision of the claw of size 3 shown in Figure 2.

Figure 2: A subdivision of a claw

Since only the relative order of the time-stamps determines influences, we assume, without loss of generality, that the time-stamps on these six edges are $\{1,2,3,4,5,6\}$. If $c(\{a,b\})=1$, then there can be no influence between $h$ and $f$. Hence $c(\{a,b\})\neq 1$. Similarly, $c(\{a,d\})\neq 1$ and $c(\{a,f\})\neq 1$. Without loss of generality, we assume that $c(\{b,h\})=1$. Now if $c(\{a,d\})=2$, then there can be no influence between $e$ and $f$. So $c(\{a,d\})\neq 2$. Similarly, $c(\{a,f\})\neq 2$. If $c(\{d,e\})=2$, then there can be no influence between $h$ and $e$. Therefore $c(\{d,e\})\neq 2$, and similarly $c(\{f,g\})\neq 2$. Thus $c(\{a,b\})=2$. Now, without loss of generality, assume that $e$ influences $g$. This forces $c(\{d,e\})=3$ and $c(\{d,a\})=4$, and now there is no influence between $e$ and $h$. This contradiction implies that $T$ must be a caterpillar. To see that every caterpillar can be a maximizer for $t_{\max}(m)$, let $w_1,w_2,\ldots,w_k$ be the (internal) vertices on the spine of the caterpillar such that $e_i=\{w_i,w_{i+1}\}$. Let $S_i=\{\;e\in E(T):$ $e$ is a leg incident to $w_i$  $\}$. Then order the edges as follows: $S_1,e_1,S_2,e_2,\ldots,e_{k-1},S_k$, and give the $i$th edge the time-stamp $i$. $\qedsymbol$

The natural question is to ask whether every number of influences in the interval $[3m-1,m(m+3)/2]$ can be achieved by a tree with $m$ edges. If the answer is yes, then a deeper question is to see whether it can be achieved by using a restricted class of trees. For example, since Theorem 2.1 shows that both the maximum and the minimum can be achieved by a path, one may also wonder whether every number is achievable by a path. The next proposition shows that the answer to this last question is no except for the trivial cases when $m=1,2,3$.

Proposition 2.2   A path with $m\geq 4$ edges and an injective time-stamp function cannot induce exactly $m(m+3)/2-1$ influences.

Proof. Suppose such a time-stamped path $(P,c)$ exists with range$(c)=\{1,2,\ldots,m\}$. Since it induces $m(m+3)/2-1$ influences, there is exactly one path of length at least 2 that induces no influence. Let the vertices on $P$ be $v_1,v_2,\ldots,v_{m+1}$ with $v_i$ adjacent to $v_{i+1}$ for $1\leq i\leq m$. Suppose $c(\{v_i,v_{i+1}\})=m$. If $i\not\in\{1,m\}$, then since $m\geq 4$, either the path from $v_1$ to $v_i$ or the path from $v_{i+1}$ to $v_{m+1}$ has length at least 2. Without loss of generality, we may assume that the path from $v_1$ to $v_i$ has length at least 2. Then neither the path from $v_1$ to $v_{m+1}$ nor the path from $v_2$ to $v_{m+1}$ induces an influence, a contradiction. Hence, without loss of generality, we may assume that $c(\{v_m,v_{m+1}\})=m$. Let $v_j$ be the farthest vertex from $v_1$ that $v_1$ influences; that is, $v_1,v_2,\ldots,v_j$ is the maximal non-decreasing subpath starting from $v_1$. Since $c(\{v_m,v_{m+1}\})=m$, we have $j\leq m-1$; otherwise, the path would induce $m(m+3)/2$ influences. Then there is no influence between $v_1$ and $v_{m+1}$ nor between $v_2$ and $v_{m+1}$ since $m\geq 4$. $\qedsymbol$

We now know that the class of paths of $m$ edges is not large enough to induce all numbers of influences in the interval $[3m-1,m(m+3)/2]$. (An interesting open problem is to find all the values that can be attained from paths.) Since the class of paths is not large enough, we must include graphs having at least one vertex of degree 3 or above. We will show that adding one such vertex of degree 3 is enough, that is, the class of trees that are homeomorphic to either $K_2$ or $K_{1,3}$ will suffice. In fact, we will show that trees with time-stamp 1 on a leaf-edge and homeomorphic to $K_2$ or $K_{1,3}$ are sufficient. We start with the following lemmas. Remember that we are always assuming that $c$ is bijective with range $\{1,2,\ldots,m\}$.

Lemma 2.3   For every integer $t$ in $[m(m+3)/2-m+2,m(m+3)/2]$, there exists $(T,c)$ where $T$ is a tree homeomorphic to $K_2$ or $K_{1,3}$ with $m$ edges and the time-stamp $1$ on a leaf-edge such that $T^{\rm I}_c$ has $t$ arcs.

Proof. We use a path on $m-1$ edges with time-stamps from 2 to $m$ as shown in Figure 3. This will create $(m-1)(m+2)/2=m(m+3)/2-m-1$ influences. We now join an additional leaf-edge to the path, with time-stamp $1$. We consider joining it to each of the $v_i$'s. If it is joined to $v_1$, then it will create $m+1$ extra influences, so the total is $m(m+3)/2$, as expected. If it is joined to $v_2$, then it will still create $m+1$ extra influences. If it is joined to $v_3$, then it will create $m$ extra influences. In general, if $2\leq i\leq m$, then attaching the new leaf-edge at $v_i$ will create $m-i+3$ extra influences, and the result follows. $\qedsymbol$

Figure 3: A caterpillar with one leg

Lemma 2.4   For every integer $t$ in $[m(m+3)/2-2m+5,m(m+3)/2-m+2]$, there exists $(T,c)$ where $T$ is homeomorphic to $K_2$ or $K_{1,3}$ with $m$ edges and the time-stamp $1$ on a leaf-edge such that $T^{\rm I}_c$ has $t$ arcs.

Proof. We use a path on $m-2$ edges with time-stamps from 2 to $m$ as shown in Figure 4. This will create $(m-2)(m+1)/2=m(m+3)/2-2m-1$ influences. We now join two additional vertices forming a path to the existing path whose edges have time-stamp $1$ and $m$, with the edge with time-stamp 1 being a leaf-edge. We consider joining this path to each of the $v_i$'s. If it is joined to $v_1$, then it will create six extra influences, so the total is $m(m+3)/2-2m+5$. If it is joined to $v_2$, then it will create seven extra influences. In general, if $1\leq i\leq m-2$, then joining this path to $v_i$ will create $i+5$ extra influences. (Note that joining the path to $v_{m-1}$ will create $m+3$ extra influences and not $m+4$.) The result follows. $\qedsymbol$

Figure 4: A caterpillar with one leg, which is then subdivided

Theorem 2.5   For every integer $t$ in $[3m-1,m(m+3)/2]$, there exists $(T,c)$ where $T$ is homeomorphic to $K_2$ or $K_{1,3}$ with $m$ edges and the time-stamp $1$ on a leaf-edge such that $T^{\rm I}_c$ has $t$ arcs.

Proof. It is easy to check that the result is true for $m\leq 2$. Let $m\geq 3$. Assume it is true for $1\leq m'\leq m-1$. Let $k$ be an integer in $[3m-1,m(m+3)/2]$. It follows from Lemmas 2.3 and 2.4 that we may assume that $k$ is in the interval $[3m-1,m(m+3)/2-2m+4]$. We claim that by the induction hypothesis, there is a tree $T$ isomorphic to $K_2$ or $K_{1,3}$ with $m-2$ edges and the time-stamp 1 on a leaf-edge inducing $k-6$ influences. To see this, we check that $k-6$ is in the interval $[3(m-2)-1,(m-2)(m+1)/2]$. This is true since $k$ is in the interval $[3m-1,m(m+3)/2-2m+4]$. Now by mapping the time-stamps of $T$ to the labels $2,3,\ldots,m-1$ in a natural way, the resulting tree still induces $k-6$ influences. We know by the induction hypothesis that the time-stamp $2$ is on a leaf-edge $\{u,v\}$ where $v$ is a leaf. We add $\{v,y\}$ with time-stamp $m$ and $\{y,z\}$ with time-stamp 1. This adds six more influences, giving $k$ influences in the new tree, as desired. $\qedsymbol$

Corollary 2.6   Let $\mathcal F$ be $\emptyset$ if $m=1$, $\{3,4\}$ if $m=2$, $\{3,6,7\}$ if $m=3$, $\{3,6,10\}$ if $m=4$, and $\{3\}$ if $m\geq 5$. Then there exists $(F,c)$ where $F$ is a nontrivial forest with $m+1$ vertices and $c$ is injective such that $F^{\rm I}_c$ has $t$ arcs if and only if $t\in [2,m(m+3)/2]\setminus\mathcal F$.

Proof. Given $m\geq 1$, we would like to construct $(F,c)$ where $F$ is a forest with $m+1$ vertices such that $T^{\rm I}_c$ has $t$ arcs. We first note that $t=3$ is not realizable. Clearly, only $t=2$ is realizable if $m=1$. Suppose $m=2$. Then the forest has 3 vertices. If it has one component, then only $t=5$ is realizable by Theorems 2.1 and 2.5. If it has two components, then one component is a tree with two vertices and the other is a singleton, and hence only $t=2$ is realizable. Suppose $m=3$. Then the forest has four vertices. If it has one component, then only $t=8,9$ are realizable. If it has two components with one component on three vertices, then only $t=5$ is realizable. If it has two components with each component having two vertices, then only $t=4$ is realizable. If it has three components, then only $t=2$ is realizable. The argument for $m=4$ is similar.

Now assume $m\geq 5$. Then by considering a forest with a component on $k+1$ vertices and $m-k$ singletons where $2\leq k\leq m$, we can deduce that each $t$ in $[3k-1,k(k+3)/2]$ is realizable. Now by considering a forest with a component on $k$ vertices and $m-k+1$ singletons, we can deduce that each $t$ in $[3k-4,(k-1)(k+2)/2]$ is realizable. Since $(k-1)(k+2)/2\geq 3k-1$ if $k\geq 5$, every $t$ in $[11,m(m+3)/2]$ is realizable. Since $m\geq 5$, we can conclude that $t=2,4,5,7,8,9$ are realizable just by considering a forest on five vertices. By taking three components having two vertices and the others being singletons, $t=6$ is realizable. Finally, by taking a component with four vertices realizing eight influences, a component with two vertices and the others being singletons, $t=10$ is realizable. $\qedsymbol$

We will also mention the following related result without proof. The point of view is from the number of edges and its proof is simpler than the proof for the previous result.

Theorem 2.7   For every integer $t$ in $[2m,m(m+3)/2]$, there exists $(F,c)$ where $F$ is a forest with $m$ edges and $c$ is injective such that $F^{\rm I}_c$ has $t$ arcs.

If $c$ is permitted to be non-injective, then the number of arcs in the associated influence digraph of a tree may fall outside $[3m-1,m(m+3)/2]$. For example, if every time-stamp is the same, then all $m(m+1)$ influences occur. However, such cases really correspond to time-stamp graphs that are not trees as seen in Section 1.