We characterize line digraphs of polytrees, including several of their well-known subclasses. For a given undirected tree, we characterize its orientations with weak line digraphs, and count the exact number. Furthermore, we find the minimum, maximum, and average sizes of these line digraphs. We provide an explicit formula for the number of weak components in line digraphs of polytrees in terms of the inner sources and sinks. Additionally, we count the average number of weak components in them among all orientations of a fixed tree. Finally, we propose an algorithm for finding weak components in line digraphs of polytrees.
For any collection of sets \(\mathcal{F}\) of arbitrary nature one can associate the corresponding intersection graph, which i s an undirected graph having \(\mathcal{F}\) as its vertex set and in which two sets \(A,B\in\mathcal{F}\) are adjacent provided \(A\cap B\neq\emptyset\). This construction is “universal” in a sense that any graph is isomorphic to the intersection graph for some family \(\mathcal{F}\). However, if we restrict ourselves to some particular collections of sets \(\mathcal{F}\), the problem of characterizing resulting intersection graphs becomes much more interesting. Among such well-known “geometric” set families are intervals on the real line [10] (interval graphs), chords on a circle [12] (circle graphs), curves on a plane [3] (string graphs) and many other similar constructions.
Graph theory itself also suggests several natural families of sets to consider for the intersection graphs. We only mention the families of edges in a graph [2] (line graphs), cliques [11] (clique graphs), blocks [7] (block graphs) etc. Thus, the line graph \(L(G)\) of a graph \(G=(V(G),E(G))\) has a vertex set \(E(G)\) with two edges being adjacent if they share a common vertex. A well-known Whitney isomorphism theorem [13] states that, apart from one trivial exception, the line graph \(L(G)\) characterizes its parent graph \(G\) uniquely (up to isomorphism). Thus, the transition to the line graph does not lose any information. Line graphs admit many nice characterizations [8, Theorem 8.4] (as do several its subclasses, for example, the line graphs of complete graphs, trees and bipartite graphs).
Moving from undirected graphs to their directed versions (shortly, digraphs), we can modify the construction of the intersection graph as follows. Let \(\mathcal{F}\) be a collection of ordered pairs of sets. The corresponding intersection digraph has elements from \(\mathcal{F}\) as vertices with two of them \((X,Y)\) and \((Z,T)\) being adjacent provided \(X\cap T\neq\emptyset\) (see [4]).
For a digraph \(D=(V(D),A(D))\), its line digraph \(L(D)\) is then defined as the intersection digraph for the family of pairs \(\mathcal{F}=\{(\{v\},\{u\}):(u,v)\in A(D)\}\). In other words, the vertices of \(L(D)\) can be identified with the arcs in \(D\) with the existence of an arc \(\alpha\rightarrow\beta\) in \(L(D)\) provided the head of \(\alpha\) is the tail of \(\beta\). Similarly to the line graphs, line digraphs also admit nice characterizations [1] (the main criterion will be presented in Theorem 2.4).
In this work, we consider the properties of line digraphs of polytrees (which are orientations of undirected trees). The paper is organized as follows.
In Section 2, we briefly give all the necessary preliminary information about undirected graphs, digraphs, and line digraphs.
In Section 3.1, we present criteria for line digraphs of polytrees (Theorem 3.1) and several of their subclasses, including in-trees (out-trees) and the orientations of paths and stars (Propositions 3.5–3.7). We also characterize polytrees which are line digraphs themselves (Proposition 3.3).
Section 3.2 is devoted to studying the polytrees with weak line digraphs. In particular, at first we characterize such polytrees (Proposition 3.8). Then, for a given tree, we find an explicit number of its orientations having weak line digraphs (Theorem 3.11). After finding the exact number of arcs in line digraphs of out-trees and in-trees (Proposition 3.12), we calculate the minimum size of \(L(T)\) among those orientations \(T\) of a given tree \(X\) which have weak \(L(T)\)’s (Theorem 3.13). Similarly, after proving that any orientation \(T\) of a given tree \(X\) which maximizes the size of \(L(T)\) necessarily has a weak \(L(T)\) (Proposition 3.14), we explicitly calculate the maximum size of such a line digraph in Theorem 3.16. Also, using the first Zagreb index, we calculate the average size of line digraphs among all orientations of a given tree.
In Section 3.3, we calculate the number of weak components in line digraphs of polytrees in terms of the inner sources and sinks (Proposition 3.19), and as a corollary, provide the average number of weak components among orientations of a given tree. We then proceed by presenting an algorithm for finding weak components in line digraphs of polytrees and justify its correctness in Theorem 3.24.
We note that some of the results from this paper were announced at International Conference of Young Mathematicians [5] in 2023.
An undirected graph or just a graph is an ordered pair \(G=(V,E)\), where \(V=V(G)\) is the set of its vertices and \(E=E(G)\) is the set of its edges. Hence, our graphs are simple, i.e. they do not have loops nor multiple edges. Also, all graphs in this paper are assumed to be finite. For convenience, we denote an edge \(\{u,v\}\) as \(uv\).
For a graph \(G\), its line graph \(L(G)\) is an intersection graph on the collection of \(E(G)\), i.e. \(V(L(G))=E(G)\) with two edges \(e_{1},e_{2}\in E(G)\) being adjacent in \(L(G)\) provided they share a vertex.
A graph is called connected if there is a path between any pair of its vertices. On the vertex set \(V(G)\) of a connected graph \(G\), one can define a metric \(d_{G}\) with \(d_{G}(u, v)\) equal to the length of the shortest path between \(u\) and \(v\). A metric interval \([u, v]_{G}\) is the set of all vertices \(w\) such that there is a shortest path between \(u\) and \(v\) containing \(w\). A set \(A\) of vertices in a graph is called convex if \([u, v]_{G}\subset A\) for all \(u, v \in A\). For any set \(A\) of vertices of \(G\), its convex hull \(\mathop{\mathrm{Conv}}_{G}(A)\) is defined as the minimal (by inclusion) convex set that contains \(A\). A set of vertices \(A\subset V(G)\) is called Chebyshev provided for any vertex \(u\in V(G)\) there exists a unique vertex \(v\in A\) with \(d_{G}(u,v)=d_{G}(u,A):=\min\{d_{G}(u,a):a\in A\}\). We denote such a vertex \(v\) by \(\mathop{\mathrm{pr}}_{A}(u)\).
A connected graph without cycles is called a tree. A path \(P_{n}\) is a connected graph whose vertices have degrees at most two. A star \(K_{1, n – 1}\) is a complete bipartite graph with one of the parts consisting of a single vertex, called the center of the star. In a tree, a vertex with a degree of one is called a leaf. We use \(\mathop{\mathrm{Leaf}}(X)\) to denote the set of all leaf vertices in \(X\).
A directed graph, often referred to as a digraph, is an ordered pair \(D=(V,A)\), where \(V=V(D)\) is the set of its vertices and \(A=A(D)\subset V\times V\) is the set of its arcs. Thus, our digraphs can have loops (arcs of the form \((u,u)\)). For an arc \(\alpha=(u,v)\) in a digraph \(D\), the vertex \(u\) is called the tail of \(\alpha\) and \(v\) is called the head of \(\alpha\). Consequently, \(\alpha\) is called an out-arc from the vertex \(u\) and an in-arc into the vertex \(v\).
The out-degree \(d^{+}_{D}(u)\) of a vertex \(u\in V(D)\) in a digraph \(D\) is the number of out-arcs from \(u\). A vertex \(u\) is called a sink if \(d^{+}_{D}(u)=0\). Similarly, the in-degree \(d^{-}_{D}(u)\) of a vertex \(u\in V(D)\) in a digraph \(D\) is the number of in-arcs into \(u\). A vertex \(u\) is called a source if \(d^{-}_{D}(u)=0\).
If \(\alpha=(u,v)\) and \(\beta=(v,w)\) are two arcs in a digraph \(D\), then we say that \(\alpha\) is adjacent to \(\beta\) and \(\beta\) is adjacent from \(\alpha\). And both \(\alpha\) and \(\beta\) are adjacent with each other. Similarly, in this case, \(u\) is adjacent to \(v\), \(v\) is adjacent from \(u\), and both are adjacent with each other. Finally, we say that \(u\) is incident to \(\alpha\), \(v\) is incident from \(\alpha\), and both vertices are incident with \(\alpha\).
A walk is a finite sequence of vertices in which every next vertex is adjacent from the previous one. A dipath is a walk with different vertices. If there exists a dipath beginning at vertex \(u\) and ending at vertex \(v\), then \(u\) is connected to \(v\), \(v\) is connected (reachable) from \(u\), and both are connected with each other. Similarly, we define connectedness for the first and last arcs of a dipath. A directed cycle is a walk in which exactly two vertices coincide – the first and the last one. The length of a directed cycle is the number of different vertices in it. Directed cycle of length \(1\) is called a loop.
For a digraph \(D\), its converse digraph is the digraph \(D^{co}\) with the vertex set \(V(D^{co})=V(D)\) and the arc set \(A(D^{co})=\{(a, b):(b, a)\in A(D)\}\).
For a digraph, \(D\) by \([D]\) we denote the corresponding undirected graph which is obtained from \(D\), i.e. \(V([D])=V(D)\) and \(E([D])=\{uv:u\neq v\ \text{and}\ (u,v)\in A(D)\ \text{or}\ (v,u)\in A(D)\}\). A digraph is called weakly connected or weak if \([D]\) is connected. A weak component of a digraph is its maximal weak subgraph. A digraph \(D\) is empty if \(A(D)=\emptyset\).
Given a digraph \(D\), its line digraph is a digraph \(L(D)\) with the vertex set \(V(L(D))=A(D)\) and the arc set \[A(L(D))=\{(\alpha,\beta)\in A(D)\times A(D):\alpha=(a,b),\beta=(b,c)\ \text{for}\ a,b,c\in V(D)\}.\]
An example of a digraph and its line digraph is given in Figure 1.
The next simple result about the size of a line digraph will be frequently used without reference.
Theorem 2.1. [9] For any digraph \(D\) we have \[|A(L(D))| = \sum_{u \in V(D)} d^{+}_{D}(u)\cdot d^{-}_{D}(u).\]
Let \(G\) be a graph. An orientation of \(G\) is any digraph \(D\) without directed cycles of length \(\leq 2\) and \([D]=G\). A polytree, polypath, polystar, polycycle is an orientation of a tree, path, star, cycle, respectively. An in-tree (out-tree) is a polytree in which all edges are oriented towards (from) some sink (source). Note that the converse digraph of an in-tree is an out-tree and vice versa.
A bipartite digraph is an orientation of a bipartite graph in which all arcs are oriented from one part (of the corresponding bipartition) to another. A two-port digraph is a bipartite digraph \(D\) with \([D]\) being a complete bipartite graph. We shall denote it as \(K(A, B)\), where \(A, B \subset V(D)\) are the corresponding parts. The next characterization is straightforward.
Proposition 2.2. A graph \(G\) is bipartite if and only if there exists its orientation \(D\) with \(L(D)\) being an empty digraph.
Proof. Necessity. Let \(A\) and \(B\) be the parts of \(G\). Construct the corresponding bipartite digraph \(D\) with every edge oriented from \(A\) to \(B\). Then \(D\) contains no dipath of length greater than one, thus \(L(D)\) is empty.
Sufficiency. Since \(L(D)\) has no arcs, every vertex of \(D\) is either a source or a sink. Let \(A\) be the set of sources of \(D\), and \(B\) the set of its sinks. Then every arc’s tail belongs to \(A\), and every arc’s head belongs to \(B\). Therefore, by neglecting the orientation of arcs we get a bipartite graph \(G\) with parts equal to \(A\) and \(B\). ◻
It is easy to see that \(L(D)\) is a directed cycle if and only if \(D\) is a directed cycle itself. The next result provides a characterization of line digraphs of other polycycles.
Proposition 2.3. For a digraph \(D\) there exists a polycycle but not a directed cycle \(C\) such that \(L(C)\simeq D\) if and only if \(D\) has an even number of weak components each being a dipath.
Proof. Necessity. As a polycycle which is not a directed cycle, \(C\) consists of \(2k\) dipaths \(W_1,W_2,\dots,W_{2k}\), where \(W_i\) and \(W_{(i + 1)\bmod{2k}}\) share the starting vertex or the endvertex. Clearly, \(L(W_1),L(W_2),\dots, L(W_{2k})\) are weak components in \(L(C)\) and each \(L(W_i)\) is a dipath of length \(|W_i| – 1\) for all \(i \in [1, 2k]\).
Sufficiency. Let \(P_{1},\dots,P_{2k}\) be the weak components of \(D\). Hence, every \(P_{i}\) is a dipath. Identify the endvertices in \(P_1\) and \(P_2\), identify starting vertices in \(P_2\) and \(P_3\), and so on alternately. Then, since \(2k\) is even, \(P_{2k}\) and \(P_1\) will share the starting vertex, and we will have built a polycycle \(C\) consisting of \(P_{1},P_{2},\dots,P_{2k}\). It is easy to see that \(L(C) = D\). ◻
Given a set \(S\), its improper partition is a collection of (possibly empty) subsets \(S_{i}\subset S\) such that \(S = \sqcup S_{i}\).
The main characterization of line digraphs is due to Harary and Norman [9].
Theorem 2.4. [9] A digraph \(D\) is a line digraph if and only if there exist two improper partitions \(A_{i}\) and \(B_{i}\) of \(V(D)\) such that \(A(D) = \bigcup_{\substack{i}} K(A_{i}, B_{i})\).
Our first result is a characterization of line digraphs of polytrees.
Theorem 3.1. Let \(D\) be a line digraph. Then there exists a polytree \(T\) with \(L(T) \simeq D\) if and only if every polycycle in \(D\) is a bipartite subgraph.
Proof. Necessity. Let \(C'\) be a polycycle in \(D\). Clearly, \(C'\) can not be a directed cycle. Thus \(C'\) consists of \(2k\) dipaths \(W'_1, W'_2,\dots, W'_{2k}\) (see Proposition 2.3) with dipaths \(W'_i\) and \(W'_{i + 1}\) being connected at a single vertex, which is either their common source or their common sink, depending on the parity of \(i\) (we shall write \(i + 1\) instead of \((i + 1) \: \bmod \: 2k\) for simplicity). Then \(L^{-1}(C')\), which is a subgraph of \(T\), consists of \(2k\) dipaths \(W_1, W_2,\dots, W_{2k}\), with \(|W_i| = |W'_i| + 1\). Also, \(W_i\) and \(W_{i + 1}\) share an arc – the very arc that generates the common vertex of \(W'_i\) and \(W'_{i + 1}\). All the arcs in \(L^{-1}(C')\), save for the shared ones, form a polycycle \(C\) whose dipaths are of length \(|W_i| – 2 = |W'_i| – 1\) (the first and last arcs of each dipath \(W_i\) are shared with other dipaths and thus not included). But there is a single case when \(|W'_i| = 1\) for all \(i \in [1, 2k]\) and \(C\) becomes a single vertex. Since \(T\) is a polytree, it contains no polycycles, so \(C\) is indeed a vertex and \(|W'_i| = 1\) for all \(i\). But that means that \(C'\) is a bipartite subgraph, with every source adjacent to both of its neighbors and every sink incident from its neighbors.
Sufficiency. As \(D\) is a line digraph, there exist two improper partitions \(A_i\) and \(B_i\) such that \(A(D) = \bigcup_{\substack{i}} K_i\), where \(K_i := K(A_i, B_i)\). Let \(E = L^{-1}(D)\). Each \(K_i\) corresponds to a vertex of \(E\). Every other vertex of \(E\) is a source or a sink; construct \(E\) in such a way that all those vertices are of degree one, therefore not a being part of a polycycle.
First we shall prove that in such a case, \(E\) has no polycycles. To the contrary, let \(C\) be a polycycle in \(E\), \(a_1-a_2-\dots-a_n-a_1\) be its vertices, and \(\alpha_i\) be the arc between \(a_i\) and \(a_{i + 1}\). As previously shown, each vertex \(a_i\) is associated with a two-port subgraph \(K_i\) of \(D\). Every arc \(\alpha_i\) corresponds to a vertex \(\alpha'_i\) of \(D\), which is common for \(K_i\) and \(K_{i + 1}\). So \(\alpha'_{i – 1}\) and \(\alpha'_i\) are distinct vertices that belong to \(K_i\). If \(\alpha'_{i – 1}\) and \(\alpha'_i\) are from different ports, then there is an arc between them. Otherwise, if they both are from port \(A_i\), there exists a polypath \(\alpha'_{i – 1}-\beta-\alpha'_i\), where \(\beta\) is any vertex from port \(B_i\) (similarly, if they are both from \(B_i\)). In every case, there is a polypath between \(\alpha'_{i – 1}\) and \(\alpha'_i\). Hence, the vertices \(\alpha'_1, \alpha'_2,\dots, \alpha'_n\) together with some intermediate vertices form a polycycle \(C'\) of \(D\). Note that \(C'\) is not a bipartite subgraph, as every weak bipartite subgraph of \(D\) is either \(K_i\) or a subgraph of \(K_i\). We have a contradiction, which implies \(E\) has no polycycles.
Assume \(E\) consists of \(k\) weak components \(E_1, E_2,\dots, E_k\). Each of them has at least one sink; let \(a_i\) be a sink that belongs to \(E_i\). By merging \(a_1,a_2,\dots,a_k\) into one vertex, we obtain a digraph \(T\) with \(L(T) = L(E) = D\). Clearly, \(T\) is weak and has no polycycles, thus it is a polytree. ◻
Example 3.2. Consider a digraph \(D\) with the vertex set \(V(D)=\{1,\dots,7\}\) and the arc set \(A(D)=\{(1,3),(2,3),(3,6),(3,7),(4,6),(4,7),(5,6),(5,7)\}\) (see Figure 2). Then \(D\) is a line digraph with improper partitions being \(A_1 = \{1, 2\}\), \(B_1 = \{3\}\), \(A_2 = \{3, 4, 5\}\), \(B_2 = \{6, 7\}\), \(A_3 = \{6, 7\}\), \(B_3 = \{1, 2, 4, 5\}\). Also, \(D\) contains three polycycles (\(4 – 6 – 3 – 7 – 4\), \(4 – 6 – 5 – 7 – 4\), and \(3 – 6 – 5 – 7 – 3\)), all of which are bipartite subgraphs. We conclude that \(D\) is a line digraph of a polytree \(T\) (depicted in Figure 2).
Next we characterize polytrees which are line digraphs themselves.
Proposition 3.3. Let \(T\) be a polytree. Then \(T\) is a line digraph if and only if for all arcs \((a, b) \in A(T)\) either \(d_{T}^{+}(a) = 1\) or \(d_{T}^{-}(b) = 1\). Moreover, this is also equivalent to the existence of a polytree \(T'\) such that \(L(T') \simeq T\).
Proof. Necessity Let \(A_{i}\) and \(B_{i}\) be two improper partitions as in Theorem 2.4, where \(i\) ranges from \(1\) to \(n\). Let \(A_{k}\) be the subset containing \(a\) and \(B_{k}\) the subset containing \(b\). Suppose \(d_{T}^{+}(a) > 1\) and \(d_{T}^{-}(b) > 1\). Then there exists a vertex \(d\) adjacent from \(a\) and a vertex \(c\) adjacent to \(b\). The vertices \(c\) and \(d\) are distinct, for otherwise \(T\) would contain a polycycle \(a – c – b – a\). Since all the arcs incident from \(a\) are contained within \(K(A_{k}, B_{k})\), it holds \(d \in B_{k}\). Similarly, \(c \in A_{k}\). Thus \(T\) contains a polycycle \(a – b – c – d – a\), a contradiction.
Sufficiency Let \((a, b)\) be an arc such that \(d_{T}^{+}(a) = 1\). Then we put \(A_{i} := N_{T}^{-}(b)\) (obviously, \(a \in A_{i}\)) and \(B_{i} := \{b\}\), so that \(K(A_{i}, B_{i})\) is the set of all arcs ending at \(b\). The case when \(d_{T}^{-}(b) = 1\) is covered similarly, that is, \(A_{i} := N_{T}^{+}(a)\) and \(B_{i} := \{b\}\). If simultaneously \(d_{T}^{+}(a) = 1\) and \(d_{T}^{-}(b) = 1\), the two processes yield the same result. It is easy to see that we thus constructed two improper partitions \(A_{i}\) and \(B_{i}\) of \(V(T)\) such that \(A(T) = \bigcup_{\substack{i}} K(A_{i}, B_{i})\). Then Theorem 2.4 implies that \(T\) is a line digraph. The existence of \(T'\) follows from Theorem 3.1. ◻
Remark 3.4. Proposition 3.3 immediately implies that a polytree is a line digraph is and only if it does not contain a “forbidden” subtree depicted in Figure 3.
We now consider several specific classes of polytrees and characterize their line digraphs.
Proposition 3.5. Let \(D\) be a digraph. Then \(D \simeq L(T)\) for an in-tree (out-tree) \(T\) if and only if every weak component of \(D\) is an in-tree (out-tree).
Proof. We shall offer proof for in-trees, considering the proof for out-trees sufficiently similar to be omitted.
Necessity. Let \(E\) be a weak component of \(D\). Additionally, let \(s\) be the unique sink of \(T\). Since \(s\) is reachable from at least one vertex of \(T\) (in fact, it is reachable from every vertex), there is an in-arc \(\alpha\) to \(s\) associated with a vertex \(\alpha'\) of \(E\). This in-arc \(\alpha\) is unique, as otherwise the connectedness of \(E\) would imply the existence of a vertex in \(T\) from which we could reach \(s\) by two different polypaths. Therefore, \(\alpha'\) is the only sink of \(E\), and so it can be reached from every vertex. Consequently, \(E\) is an in-tree.
Sufficiency. Let again \(E\) be a weak component of \(D\). As it is an in-tree, there is no vertex of \(E\) with out-degree greater than one, as otherwise there would be two different dipaths from it to \(s\), \(s\) being the sink of \(E\). It follows from Proposition 3.3 that there exists a polytree \(F\) such that \(L(F) = E\). If \(\alpha\) is the arc of \(F\) associated with \(s\), then it is reachable from every other arc of \(F\). Thus vertex \(b\) of \(F\), which is incident from \(\alpha\), is reachable from every other vertex of \(F\). Hence, \(F\) is an in-tree. Now let \(F_1,F_2,\dots,F_n\) be in-trees for which \(L(F_i) \simeq E_i\) for all \(i \in [1, n]\), \(E_i\) being the weak components of \(D\). Let all \(F_i\)’s have a common sink \(b\), and let it be the only common vertex of different \(F_i\) (therefore there will be no common arcs). This way we obtain a digraph \(T\), which is still an in-tree. Also, \(L(T) \simeq D\), which completes the proof. ◻
Proposition 3.6. Let \(D\) be a digraph. Then \(D \simeq L(T)\) for a polypath \(T\) if and only if every weak component of \(D\) is a dipath.
Proof. Necessity. By definition, a polypath is given by a sequence of dipaths where each two consecutive paths share a common vertex (alternately starting and ending vertices). After taking the line digraph, every dipath of length \(k\) will become a separate weak component, which by itself is a dipath of length \(k – 1\). That completes the proof.
Sufficiency. Let \(D_1,D_2,\dots,D_n\) be the weak components of \(D\), each of them being a dipath of length \(k_1,k_2,\dots,k_n\), respectively. Let \(T_i\), \(i \in [1, n]\) be digraphs such that \(D_i = L(T_i)\) for all \(i \in [1, n]\). Then every \(T_i\) is a dipath of length \(k_i + 1\). Let a digraph \(T\) be a sequence of \(T_1,T_2,\dots,T_n\) with \(T_1\) and \(T_2\) sharing an endvertex, \(T_2\) and \(T_3\) sharing the starting vertex, and so on alternately. Then \(T\) is a polypath with \(L(T) = D\). ◻
Proposition 3.7. Let \(D\) be a digraph. Then \(D \simeq L(S)\) for a polystar \(S\) if and only if \(D\) is either a two-port digraph or an empty digraph.
Proof. Necessity. If the center \(p\) of \(S\) is either the common source or the common sink of all its arcs, then \(D\) is empty. Otherwise, let \(\alpha_1,\alpha_2,\dots,\alpha_n\) be arcs ending at \(p\), and \(\beta_1,\beta_2,\dots,\beta_m\) be arcs starting at \(p\). Let \(a_1,\dots,a_n\), \(b_1,\dots,b_m\) be corresponding vertices of \(D = L(S)\). Then \(D\) is a two-port digraph, its ports being \(A = \{a_1,a_2,\dots,a_n\}\) and \(B = \{b_1,b_2,\dots,b_m\}\). So \(D\) is either a two-port or an empty digraph.
Sufficiency. If \(D\) is a two-port digraph, then \(S\) is a vertex together with arcs incident to and from it (which is a polystar). If \(D\) is empty with \(n\) vertices, then \(D = L(S)\) for a polystar \(S\) with \(n\) arcs, all of them adjacent to (or all adjacent from) the center. In any case, \(D\) is a line digraph of a polystar. ◻
We begin by giving a characterization of polytrees with weak line digraphs.
Proposition 3.8. Let \(T\) be a polytree. Then \(L(T)\) is weak if and only if every source and every sink of \(T\) is a leaf in \([T]\).
Proof. Necessity. Let \(s\) be the source in \(T\) of out-degree \(m\geq 2\) (the proof is similar for a sink). As \(T\) is a polytree, there is no vertex to which we could get from \(s\) by two different polypaths; thus each of the neighbors of \(s\) belongs to a different induced subgraph, all the subgraphs sharing exactly one vertex, \(s\). In \(L(T)\) these subgraphs will become different weak components.
Sufficiency. Divide the arcs of \(T\) into two non-empty subsets \(A \sqcup B = A(T)\). As \(T\) is weak, there is a vertex \(a\) and two arcs \(\alpha \in A, \beta \in B\) such that \(a\) is incident with both \(\alpha\) and \(\beta\). Since \(a\) is not a source nor a sink, we may presume that \(a\) is incident from \(\alpha\) to \(\beta\) (if, for instance, \(\alpha\) and \(\beta\) are both in-arcs at \(a\), then, as \(a\) a is not a sink, there exists \(\gamma \in B\) such that \(\gamma\) is an out-arc at \(a\) (if \(\gamma \in A\), swap \(A\) and \(B\)); in that case \(\beta := \gamma\)). Let \(A'\) be the set of vertices of \(L(T)\) generated by the arcs from \(A\), and let \(B'\) be the set of vertices generated by the arcs from \(B\). Then \(A' \sqcup B' = V(L(T))\). It is easy to see that there is an arc between \(A'\) and \(B'\) – this is the arc between vertices which correspond to \(\alpha\) and \(\beta\). Since every such pair of sets \(A'\) and \(B'\) can be obtained in a similar way, this means that for every such partition of vertices of \(L(T)\) into two sets, there is an arc between vertices from different sets. This implies that \(L(T)\) is weak. ◻
Proposition 3.8 asserts that for an (undirected) tree \(X\) any its orientation \(T\) with weak \(L(T)\) gives a non-trivial partition of \(\mathop{\mathrm{Leaf}}(X)\) into two subsets (the sets of sources and sinks of \(T\)). The next result shows the converse is also true, i.e. that for any non-trivial partition of the set \(\mathop{\mathrm{Leaf}}(X)\) there is a corresponding orientation \(T\) of \(X\).
Proposition 3.9. Let \(X\) be a tree with \(|V(X)|\geq 2\) and \(\mathop{\mathrm{Leaf}}(X)=A\sqcup B\) be a partition of its leaf vertices. Then there is an orientation \(T\) of \(X\) having \(A\) as the set of its sources and \(B\) as the set of its sinks if and only if \(A\) and \(B\) both are nonempty sets.
Proof. Necessity. It is clear that every acyclic digraph (in particular, a polytree) with at least two vertices has a source as well as a sink.
Sufficiency. Assume that \(A,B\neq\emptyset\). Consider the convex hull \(C=\mathop{\mathrm{Conv}}_{X}(B)\) of \(B\). Since \(B\neq\emptyset\), then trivially \(C\neq\emptyset\) as well. Further, since \(A\neq\emptyset\), we can fix a vertex \(x_{0}\in A\). Since \(C\) is convex, it is also connected, which in case of a tree means \(C\) has to be Chebyshev. Thus we can construct an orientation \(T\) of \(X\) as follows: orient the subtree \(X[C]\) as an out-tree from the root \(\mathop{\mathrm{pr}}_{C}(x_{0})\) and orient each edge \(uv\in E(X)\backslash E(C)\) as \(u\rightarrow v\) if \(v\in[u,\mathop{\mathrm{pr}}_{C}(u)]_{X}\) (i.e. we orient the edge \(uv\) “towards” \(C\)). Since \(T[C]\) is an out-tree rooted at a non-leaf vertex \(\mathop{\mathrm{pr}}_{C}(x_{0})\) in \(X\), it is clear that the elements of \(\mathop{\mathrm{Leaf}}(X[C])\) are exactly the sinks in \(T[C]\). Hence, the inclusion \(B\subset\mathop{\mathrm{Leaf}}(X[C])\cap\mathop{\mathrm{Leaf}}(X)\) implies that the elements of \(B\) are sinks in \(T\) as well.
Now consider a vertex \(u\in A\) and the corresponding leaf edge \(uv\in E(X)\) (clearly \(uv \not \in E(C)\)). By construction of \(T\), we have \((u,v)\in A(T)\) which implies that \(u\) is a source in \(T\). Therefore, the elements of \(A\) are the sources in \(T\).
Now we only need to show that there are no other sources or sinks in \(T\). Indeed, since \(T[C]\) is an out-tree, any non-leaf vertex in \(X[C]\) is not a source nor a sink in \(T\). Also, the minimality of \(C\) implies \(\mathop{\mathrm{Leaf}}(X[C])=B\), thus no element of \(C \backslash B\) can be a source or a sink. Finally, assume that \(y\in V(X)\backslash(C\cup A)\). Then \(y\) has two neighbors \(u,v\in N_{X}(y)\) with \(y\in[u,\mathop{\mathrm{pr}}_{C}(u)]_{X}\) and \(v\in[y,\mathop{\mathrm{pr}}_{C}(y)]_{X}\). By construction, \((u,y),(y,v)\in A(T)\) implying that \(y\) also is not a source nor a sink in \(T\). ◻
Example 3.10. Consider a tree \(X\) with the vertex set \(V(X)=\{1,\dots,8\}\) and the edge set \(E(X)=\{12,23,26,34,37,38,45,56\}\). Consider a partition of \(\mathop{\mathrm{Leaf}}(X)=\{1,5,6,7,8\}\) into two sets \(A=\{5,6,8\}\) and \(B=\{1,7\}\). We have that \(C:=\mathop{\mathrm{Conv}}_{X}(B)=\{1,2,3,7\}\). Fix a vertex \(x_{0}=8\in A\) and orient \(X\) as in proof of Proposition 3.9: the subtree \(X[C]\) is oriented as an out-tree from the root \(\mathop{\mathrm{pr}}_{C}(x_{0})=3\) and other edges are oriented towards \(X[C]\) (see Figure 4). It is clear that the sources of this orientation are exactly the vertices from \(A\) and the sinks are the vertices from \(B\).
In fact, for a given tree \(X\), we can explicitly calculate the number of orientations of \(X\) having weak line digraphs. Note that this number depends only on the degree sequence of \(X\) and not on its structure.
Theorem 3.11. Let \(X\) be a tree with \(n\geq 3\) vertices. Then the number of orientations of \(T\) having weak line digraphs equals \[2\cdot\prod_{{\substack{u\in V(X)\backslash\mathop{\mathrm{Leaf}}(X)}}}(2^{d_{X}(u)-1}-1).\]
Proof. Let us call an orientation \(T\) of \(X\) good if \(L(T)\) is weak.
We use induction on the number of non-leaf vertices in \(X\). First, note that since \(n\geq 3\), \(X\) has at least one such vertex. If \(|V(X)\backslash\mathop{\mathrm{Leaf}}(X)|=1\), then \(X\simeq K_{1,n-1}\) is a star. And among \(2^{n-1}\) orientations of \(X\) exactly two orientations have the center of \(X\) as a source or a sink. By Proposition 3.8, they yield a disconnected line digraph. Hence, in case of a star, there are \(2^{n-1}-2=2(2^{(n-1)-1}-1)\) good orientations \(T\) of \(X\).
Further, assume \(|V(X)\backslash\mathop{\mathrm{Leaf}}(X)|\geq 2\). Then there exists a vertex \(v_{0}\in\mathop{\mathrm{Leaf}}(X\backslash\mathop{\mathrm{Leaf}}(X))\). Consider the tree \(X'=X\backslash(N_{X}(v_{0})\cap\mathop{\mathrm{Leaf}}(X))\) which is obtained from \(X\) by deleting all \(d_{X}(v_{0})-1\) leaf neighbors of \(v_{0}\). Since \(v_{0}\) is a leaf vertex in \(X'\), the tree \(X'\) has fewer non-leaf vertices than \(X\).
By induction assumption, the number of good orientations of \(X'\) equals \[2\cdot\prod_{{\substack{u\in V(X')\backslash\mathop{\mathrm{Leaf}}(X')}}}(2^{d_{X'}(u)-1}-1)=2\cdot\prod_{{\substack{u\in V(X)\backslash(\mathop{\mathrm{Leaf}}(X)\cup\{v_{0}\})}}}(2^{d_{X}(u)-1}-1).\]
Proposition 3.8 immediately asserts that each good orientation \(T\) of \(X\) induces the corresponding good orientation \(T'=T\backslash\{v_{0}x:x\in N_{X}(v_{0})\cap\mathop{\mathrm{Leaf}}(X)\}\) of \(X'\). Hence, in order to calculate the number of good orientations of \(X\), we need to calculate how many of them induce the same good orientation \(T'\) of \(X'\).
Therefore, let us fix a good orientation \(T'\) of \(X'\). Overall there are \(2^{d_{X}(v_{0})-1}\) orientations \(T\) of \(X\) having \(T'\) as a suborientation. Among them only one orientation has \(v_{0}\) as a source or a sink (depending on the orientation in \(T'\) of the unique edge incident to \(v_{0}\) in \(X'\)). Thus, for a given \(T'\) we have exactly \(2^{d_{X}(v_{0})-1}-1\) corresponding good orientations \(T\). This implies that the number of good orientations of \(X\) equals \[2\cdot\prod_{{\substack{u\in V(X)\backslash(\mathop{\mathrm{Leaf}}(X)\cup\{v_{0}\})}}}(2^{d_{X}(u)-1}-1)\cdot(2^{d_{X}(v_{0})-1}-1)=2\cdot\prod_{{\substack{u\in V(X)\backslash\mathop{\mathrm{Leaf}}(X)}}}(2^{d_{X}(u)-1}-1).\] ◻
Now we turn our attention to the orientations of trees which are extremal with respect to the number of arcs in their line digraphs. But at first, we explicitly calculate the number of arcs in \(L(T)\) for out-trees and in-trees \(T\).
Proposition 3.12. If \(T\) is an \(n\)-vertex out-tree or an in-tree rooted at \(u\), then \(|A(L(T))|=n-1-d_{[T]}(u)\).
Proof. As \(|A(D)|=|A(D^{co})|\) and \((L(D))^{co}=L(D^{co})\) for any digraph \(D\), we only consider the case of out-trees \(T\). Thus let \(T\) be an out-tree rooted at \(u\). Then \(d_{T}^{+}(u)=d_{[T]}(u)\) and \(d_{T}^{-}(u)=0\). Further, for all \(x\in V(T)\backslash\{u\}\) it holds \(d_{T}^{+}(x)=d_{[T]}(x)-1\) and \(d_{T}^{-}(x)=1\). Therefore, \[\begin{aligned} |A(L(T))|&=\sum\limits_{{\substack{x\in V(T)}}}d_{T}^{+}(x)\cdot d_{T}^{-}(x)\\ &=d_{T}^{+}(u)\cdot d_{T}^{-}(u)+\sum\limits_{{\substack{x\in V(T)\backslash\{u\}}}}d_{T}^{+}(x)\cdot d_{T}^{-}(x)\\ &=\sum\limits_{{\substack{x\in V(T)\backslash\{u\}}}}(d_{[T]}(x)-1)=\sum\limits_{{\substack{x\in V(T)\backslash\{u\}}}}d_{[T]}(x)-(n-1)\\ &=(2(n-1)-d_{[T]}(u))-n+1=n-1-d_{[T]}(u). \end{aligned}\] ◻
From Proposition 2.2 it follows that any tree \(X\) admits an orientation \(T\) with \(|A(L(T))|=0\). However, if we restrict ourselves to the orientations with weak line digraphs, we obtain the following result.
Theorem 3.13. Let \(X\) be an \(n\)-vertex tree, \(n\geq 2\). Then the minimum number of arcs in \(L(T)\) among orientations \(T\) of \(X\) with weak \(L(T)\)’s equals \(n-2\).
Proof. Consider an orientation \(T\) of \(X\) which is an out-tree rooted at some leaf vertex \(u\in\mathop{\mathrm{Leaf}}(X)\). By Proposition 3.12, \(|A(L(T))|=n-1-d_{[T]}(u)=n-1-1=n-2\). Also, by Proposition 3.8, \(L(T)\) is weak. Hence, the minimum number of arcs in \(L(T)\) among orientations \(T\) of \(X\) with weak \(L(T)\)’s is at most \(n-2\). We need to show that any such orientation \(T\) has at least \(n-2\) arcs in \(L(T)\). To do so, we use induction on \(n\geq 2\). If \(n=2\), then \(X=P_{2}\) and for any orientation \(T\) of \(X\) it clearly holds \(|A(L(T))|=0=2-2\).
Now let \(n\geq 3\). At first, assume that \(X\) is a star centered at \(u\). Then \(|A(L(T))|=d_{T}^{+}(u)\cdot d_{T}^{-}(u)\). It is clear, that this number is minimized only if \(\min\{d_{T}^{+}(u),d_{T}^{-}(u)\}=1\). In this case, \(|A(L(T))|=n-2\) as \(d_{T}^{+}(u)+d_{T}^{-}(u)=|E(X)|=n-1\). Further, assume that \(X\) is not a star. This means that \(\mathop{\mathrm{Leaf}}(X-\mathop{\mathrm{Leaf}}(X))\neq\emptyset\). Fix a vertex \(v\in\mathop{\mathrm{Leaf}}(X-\mathop{\mathrm{Leaf}}(X))\) and consider a tree \(X'=X-(N_{X}(v)\cap\mathop{\mathrm{Leaf}}(X))\). It is clear that \(|V(X')|\geq 2\). Thus by induction assumption, the number of arcs in \(L(T')\) among orientations \(T'\) of \(X'\) with weak \(L(T')\)’s is at least \(|V(X')|-2=n-(d_{X}(v)-1)-2=n-1-d_{X}(v)\). Since \(v\in\mathop{\mathrm{Leaf}}(X-\mathop{\mathrm{Leaf}}(X))\), there is a unique vertex \(w\in V(X')\) with \(e=vw\in E(X')\). If \(e\) is oriented in \(T'\) as \(w\rightarrow v\), then every edge \(vx\), \(x\in N_{X}(v)\cap\mathop{\mathrm{Leaf}}(X)\) must be oriented in \(T\) as \(v\rightarrow x\) (since \(L(T)\) is weak). Similarly, if \(e\) is oriented in \(T'\) as \(v\rightarrow w\), then each edge \(vx\), \(x\in N_{X}(v)\cap\mathop{\mathrm{Leaf}}(X)\) is oriented in \(T\) as \(x\rightarrow v\). In both cases, we obtain \[|A(L(T))|\geq|A(L(T'))|+|N_{X}(v)\cap\mathop{\mathrm{Leaf}}(X)|\geq n-1-d_{X}(v)+(d_{X}(v)-1)=n-2.\] ◻
Now we consider orientations of trees with maximum number of arcs in their line digraphs. At first, we show that any such an orientation \(T\) must have a weak \(L(T)\).
Proposition 3.14. Let \(T\) be an orientation of a tree \(X\) which has a maximum number of arcs in \(L(T)\) among all orientations of \(X\). Then \(L(T)\) is weak.
Proof. To the contrary, assume that \(T\) is such an orientation of \(X\), but with a non-weak line digraph \(L(T)\). By Proposition 3.8, there is a non-leaf vertex \(u\in V(X)\backslash\mathop{\mathrm{Leaf}}(X)\) which is a source or a sink in \(T\). Without loss of generality, assume that \(u\) is a source in \(T\). Fix a vertex \(x\in N_{X}(u)\) and consider the forest \(X-\{ux\}\). Let \(X'\) be the connected component in \(X-\{ux\}\) which contains \(x\). Consider the new orientation \(T'\) of \(X\) which coincides with \(T\) on edges from \(E(X)\backslash(E(X')\cup\{ux\})\) and is opposite on edges from \(E(X')\cup\{ux\}\). In other words, we take \(T\) and conversely reorient the edges from \(E(X')\cup\{ux\}\). Then for all \(v\in V(X)\backslash(V(X')\cup\{u\})\) we have \(d_{T'}^{+}(v)=d_{T}^{+}(v)\) and \(d_{T'}^{-}(v)=d_{T}^{-}(v)\). Also, for all \(v\in V(X')\) it holds \(d_{T'}^{+}(v)=d_{T}^{-}(v)\) and \(d_{T'}^{-}(v)=d_{T}^{+}(v)\). Moreover, \(d_{T'}^{+}(u)=d_{X}(u)-1=d_{T}^{+}(u)-1\) and \(d_{T'}^{-}(u)=1=d_{T}^{-}(u)+1\). Hence, \[\begin{aligned} |A(L(T'))|=&\sum\limits_{{\substack{v\in V(T')}}}d_{T'}^{+}(v)\cdot d_{T'}^{-}(v)=\sum\limits_{{\substack{v\in V(X)\backslash(V(X')\cup\{u\})}}}d_{T'}^{+}(v)\cdot d_{T'}^{-}(v)\\ &+\sum\limits_{{\substack{v\in V(X')}}}d_{T'}^{+}(v)\cdot d_{T'}^{-}(v)+d_{T'}^{+}(u)\cdot d_{T'}^{-}(u)\\ =&\sum\limits_{{\substack{v\in V(X)\backslash(V(X')\cup\{u\})}}}d_{T}^{+}(v)\cdot d_{T}^{-}(v)+\sum\limits_{{\substack{v\in V(X')}}}d_{T}^{-}(v)\cdot d_{T}^{+}(v)+d_{X}(u)-1\\ =&\sum\limits_{{\substack{v\in V(T)\backslash\{u\}}}}d_{T}^{+}(v)\cdot d_{T}^{-}(v)+d_{X}(u)-1=\sum\limits_{{\substack{v\in V(T)}}}d_{T}^{+}(v)\cdot d_{T}^{-}(v)+d_{X}(u)-1\\ =&|A(L(T))|+d_{X}(u)-1\geq|A(L(T))|+1. \end{aligned}\]
Thus \(L(T')\) has more arcs than \(L(T)\). The obtained contradiction proves the proposition. ◻
Example 3.15. Consider a tree \(X\) with \(V(X)=\{1,\dots,7\}\), \(E(X)=\{12,23,34,37,45,46\}\) and its orientation \(T\) depicted in Figure 5.
Then the line digraph \(L(T)\) has \(3\) arcs. Since the vertex \(3\) is a source in \(T\), we can reorient \(X\) to obtain a polytree \(T'\) with more arcs in \(L(T')\). Indeed, exploiting the idea in proof of Proposition 3.14, we fix an arbitrary edge incident to \(3\), say \(34\). Then we consider the forest \(X-\{ux\}\) and its connected component \(X'\) which contains the vertex \(4\). Clearly, \(X'=X[\{4,5,6\}]\). Let us reorient the edges from \(E(X')\cup\{34\}=\{34,45,46\}\) in the opposite way to obtain the new orientation \(T'\) of \(X\) (see Figure 6). We have \(|A(T')|=5>3=|A(T)|\).
It turns out that we can explicitly calculate the maximum number of arcs in \(L(T)\)’s among orientations \(T\) of a given tree \(X\) in terms of the degrees of vertices in \(X\).
Theorem 3.16. Let \(X\) be a tree. Then the maximum number of arcs in \(L(T)\) among orientations \(T\) of \(X\) equals \[\sum\limits_{u\in V(X)}\left\lfloor\frac{d_{X}(u)}{2}\right\rfloor\cdot\left\lceil\frac{d_{X}(u)}{2}\right\rceil.\]
Proof. Let \(T\) be an orientation of \(X\). Since for every vertex \(u\in V(X)\) we have \(d_{T}^{+}(u)+d_{T}^{-}(u)=d_{X}(u)\), then \(d_{T}^{+}(u)\cdot d_{T}^{-}(u)\leq\left\lfloor\frac{d_{X}(u)}{2}\right\rfloor\cdot\left\lceil\frac{d_{X}(u)}{2}\right\rceil\). Therefore, \[|A(L(T))|=\sum_{{\substack{u \in V(T)}}}d_{T}^{+}(u)\cdot d_{T}^{-}(u)\leq\sum\limits_{u\in V(X)}\left\lfloor\frac{d_{X}(u)}{2}\right\rfloor\cdot\left\lceil\frac{d_{X}(u)}{2}\right\rceil.\]
To show that there exists an orientation which attains this bound, we again use the same induction on \(|V(X)|\geq 1\) as in proof of Theorem 3.13. The cases \(|V(X)|=1\) and \(|V(X)|=2\) are trivial. Now assume that \(|V(X)|\geq 3\). If \(X\) is a star, then divide \(\mathop{\mathrm{Leaf}}(X)=A\sqcup B\) into two almost equal parts \(A\) and \(B\) with \(|A|=\left\lfloor\frac{n-1}{2}\right\rfloor\), \(B=\left\lceil\frac{n-1}{2}\right\rceil\). Consider the orientation \(T\) of \(X\) with the vertices from \(A\) being sources and the vertices from \(B\) being sinks in it. Clearly, \[|A(L(T))|=|A|\cdot|B|=\left\lfloor\frac{n-1}{2}\right\rfloor\cdot\left\lceil\frac{n-1}{2}\right\rceil=\sum\limits_{u\in V(X)}\left\lfloor\frac{d_{X}(u)}{2}\right\rfloor\cdot\left\lceil\frac{d_{X}(u)}{2}\right\rceil.\]
Now suppose that \(X\) is not a star. Then there is a vertex \(v\in\mathop{\mathrm{Leaf}}(X-\mathop{\mathrm{Leaf}}(X))\). Consider the tree \(X'=X-(N_{X}(v)\cap\mathop{\mathrm{Leaf}}(X))\). It is clear that \(|V(X')|\geq 2\). By induction assumption, there exists an orientation \(T'\) of \(X'\) with \(|A(L(T'))|=\sum\limits_{u\in V(X')}\left\lfloor\frac{d_{X'}(u)}{2}\right\rfloor\cdot\left\lceil\frac{d_{X'}(u)}{2}\right\rceil\). We want to construct the desired orientation \(T\) of \(X\) as an extension of \(T'\), thus we only need to properly orient the edges \(vx\) for \(x\in N_{X}(v)\cap\mathop{\mathrm{Leaf}}(X)\). To do this, divide the set \(N_{X}(v)\cap\mathop{\mathrm{Leaf}}(X)=A\sqcup B\) into two almost equal parts \(A\) and \(B\) with \(|A|=\left\lfloor\frac{d_{X}(v)-1}{2}\right\rfloor\) and \(|B|=\left\lceil\frac{d_{X}(v)-1}{2}\right\rceil\). Since \(v\in\mathop{\mathrm{Leaf}}(X-\mathop{\mathrm{Leaf}}(X))\), there is a unique vertex \(w\in V(X')\) with \(vw\in E(X')\). If the edge \(vw\) is oriented in \(T'\) as \(w\rightarrow v\), then for every \(a\in A\) orient each edge \(va\) as \(a\rightarrow v\) and for every \(b\in B\) orient each edge \(vb\) as \(v\rightarrow b\) (see Figure 7). The obtained orientation \(T\) of \(X\) yields \[\begin{aligned} |A(L(T))|&=|A(L(T'))|+d_{T}^{+}(v)\cdot d_{T}^{-}(v)=|A(L(T'))|+(|A|+1)\cdot|B| \\ &=|A(L(T'))|+\left\lceil\frac{d_{X}(v)}{2}\right\rceil\cdot\left\lfloor\frac{d_{X}(v)}{2}\right\rfloor \\ &=\sum\limits_{u\in V(X')}\left\lfloor\frac{d_{X'}(u)}{2}\right\rfloor\cdot\left\lceil\frac{d_{X'}(u)}{2}\right\rceil+\left\lceil\frac{d_{X}(v)}{2}\right\rceil\cdot\left\lfloor\frac{d_{X}(v)}{2}\right\rfloor \\ &=\sum\limits_{u\in V(X')\backslash\{v\}}\left\lfloor\frac{d_{X}(u)}{2}\right\rfloor\cdot\left\lceil\frac{d_{X}(u)}{2}\right\rceil+\left\lceil\frac{d_{X}(v)}{2}\right\rceil\cdot\left\lfloor\frac{d_{X}(v)}{2}\right\rfloor \\ &=\sum\limits_{u\in V(X)}\left\lfloor\frac{d_{X}(u)}{2}\right\rfloor\cdot\left\lceil\frac{d_{X}(u)}{2}\right\rceil. \end{aligned}\]
Similarly, if the edge \(vw\) is oriented in \(T'\) as \(v\rightarrow w\), then for every \(a\in A\) orient each edge \(va\) as \(v\rightarrow a\) and for every \(b\in B\) orient each edge \(vb\) as \(b\rightarrow v\). The obtained orientation \(T\) of \(X\) also yields the desired equality \(|A(L(T))|=\sum\limits_{u\in V(X)}\left\lfloor\frac{d_{X}(u)}{2}\right\rfloor\cdot\left\lceil\frac{d_{X}(u)}{2}\right\rceil\). ◻
It turns out that it is possible to explicitly calculate the average number of arcs in line graphs \(L(T)\) among orientations \(T\) on a given tree \(X\). To present this result, we need to recall the definition of one well-known topological index. Namely, for a graph \(G\), the number \(M_{1}(G)=\sum\limits_{{\substack{x\in V(G)}}}d^{2}_{G}(x)\) is called the first Zagreb index of \(G\).
Proposition 3.17. Let \(X\) be a tree with \(n\) vertices. Then the average number of arcs in \(L(T)\) among orientations \(T\) of \(X\) equals \[\frac{M_{1}(X)}{4}-\frac{n-1}{2}.\]
Proof. We use the standard counting argument. Denote by \(\mathcal{T}(X)\) the class of all orientations of \(X\) (i.e., polytrees \(T\) with \([T]=X\)). It is clear that \(|\mathcal{T}(X)|=2^{n-1}\). In order to calculate the sum \(\sum_{T\in\mathcal{T}(X)}|A(L(T))|\), for a fixed possible arc \((e_{1},e_{2})\), we calculate the number of trees \(T\in\mathcal{T}(X)\) with \((e_{1},e_{2})\in A(L(T))\). Indeed, to be an arc in some \(L(T)\), the pair \((e_{1},e_{2})\) must consist of two adjacent edges \(e_{1}\), \(e_{2}\) in \(X\). It is clear that the number of such pairs equals the number of \(2\)-paths on \(X\). Every such path is encoded by its middle vertex, say \(x\in V(X)\), and an ordered pair \((u,v)\) of its neighbors \(u,v\in N_{X}(x)\). Hence, the number of such pairs equals \[\sum_{{\substack{x\in V(X)}}}d_{X}(x)(d_{X}(x)-1)=M_{1}(X)-2(n-1).\] Further, given an arc \((e_{1},e_{2})\), we have exactly \(2^{n-1-2}=2^{n-3}\) trees \(T\in\mathcal{T}(X)\) with \((e_{1},e_{2})\in A(L(T))\). Therefore, the average number of arcs in \(L(T)\) among orientations \(T\) on \(X\) equals \[\frac{(M_{1}(X)-2(n-1))\cdot 2^{n-3}}{2^{n-1}}=\frac{M_{1}(X)}{4}-\frac{n-1}{2}.\] ◻
Corollary 3.18. Let \(X\) be a tree with \(n\) vertices. Then the average number of arcs in \(L(T)\) among orientations \(T\) of \(X\) is at least \(\frac{n-2}{2}\) and at most \(\frac{(n-1)(n-2)}{4}\).
Proof. These bounds follow from the corresponding bounds on \(M_{1}(X)\) for trees. Namely, by [6], for an \(n\)-vertex tree \(X\) it holds that \(M_{1}(P_{n})\leq M_{1}(X)\leq M_{1}(K_{1,n-1})\). Given that \(M_{1}(P_{n})=4n-6\) and \(M_{1}(K_{1,n-1})=n(n-1)\), the result immediately follows from Proposition 3.17. ◻
Denote by \(\mathop{\mathrm{Si}}(D)\) and \(\mathop{\mathrm{So}}(D)\) the sets of sinks and sources in a digraph \(D\), respectively.
Proposition 3.19. Let \(T\) be a polytree with \(n\geq 2\). Then the number of weak components in \(L(T)\) equals \[\sum_{{\substack{u\in\mathop{\mathrm{Si}}(T)\cup\mathop{\mathrm{So}}(T)}}}(d_{[T]}(u)-1)+1.\]
Proof. Denote the number of weak components in a digraph \(D\) as \(k(D)\). We use induction on \(|\mathop{\mathrm{Si}}(T)\cup\mathop{\mathrm{So}}(T)|\geq|\mathop{\mathrm{Leaf}}([T])|\). If \(|\mathop{\mathrm{Si}}(T)\cup\mathop{\mathrm{So}}(T)|=|\mathop{\mathrm{Leaf}}([T])|\), then by Proposition 3.8, \(L(T)\) is weak implying that \(k(L(T))=1=\sum_{u\in\mathop{\mathrm{Si}}(T)\cup\mathop{\mathrm{So}}(T)}(d_{[T]}(u)-1)+1\).
Now assume that \(T\) has a sink or a source which is a non-leaf vertex in \([T]\). Without loss of generality, assume that \(x\in\mathop{\mathrm{So}}(T)\backslash\mathop{\mathrm{Leaf}}([T])\). Delete \(x\) from \(T\) and add new vertices \(x_{u}\) with new arcs \(x_{u}\rightarrow u\) for all out-neighbors \(u\in N_{T}^{+}(x)\). Denote the obtained digraph by \(T'\). It is clear that \(T'\) has exactly \(d=d_{T}^{+}(x)\) weak components \(T_{1},\dots,T_{d}\), each being a polytree with fewer sinks and sources than \(T\). By induction assumption, \(k(L(T_{i}))=\sum_{u\in\mathop{\mathrm{Si}}(T_{i})\cup\mathop{\mathrm{So}}(T_{i})}(d_{[T_{i}]}(u)-1)+1\). Since \(x\) is a source in \(T\), it is pretty straightforward to see that \(k(L(T))=\sum_{i=1}^{d}k(L(T_{i}))\). Also, \[\mathop{\mathrm{Si}}(T)\cup\mathop{\mathrm{So}}(T)=\left(\{x\}\cup\Bigl(\bigcup_{i=1}^{d}\bigl(\mathop{\mathrm{Si}}(T_{i})\cup\mathop{\mathrm{So}}(T_{i})\bigr)\Bigr)\right)\backslash\{x_{u}:u\in N_{T}^{+}(x)\}.\]
Therefore,
\[\begin{aligned} k(L(T))&=\sum_{i=1}^{d}k(L(T_{i}))=\sum_{i=1}^{d}\left(\sum_{u\in\mathop{\mathrm{Si}}(T_{i})\cup\mathop{\mathrm{So}}(T_{i})}(d_{[T_{i}]}(u)-1)+1\right)\\ &=\sum_{{\substack{u\in\bigcup_{i=1}^{d}(\mathop{\mathrm{Si}}(T_{i})\cup\mathop{\mathrm{So}}(T_{i}))}}}(d_{[T_{i}]}(u)-1)+d\\ &=\sum_{{\substack{u\in\left(\bigcup_{i=1}^{d}(\mathop{\mathrm{Si}}(T_{i})\cup\mathop{\mathrm{So}}(T_{i}))\right)\backslash\{x_{u}:u\in N_{T}^{+}(x)\}}}}(d_{[T_{i}]}(u)-1)+d\\ &=\sum_{{\substack{u\in(\mathop{\mathrm{Si}}(T)\cup\mathop{\mathrm{So}}(T))\backslash\{x\}}}}(d_{[T]}(u)-1)+(d-1)+1=\sum_{{\substack{u\in\mathop{\mathrm{Si}}(T)\cup\mathop{\mathrm{So}}(T)}}}(d_{[T]}(u)-1)+1. \end{aligned}\] ◻
Corollary 3.20. Let \(X\) be a tree. Then the average number of weak components in \(L(T)\) among orientations \(T\) of \(X\) equals \[\sum_{{\substack{u\in V(X)}}}\frac{d_{X}(u)-1}{2^{d_{X}(u)-1}}+1.\]
Proof. Let \(|V(X)|=n\). Recall that by \(\mathcal{T}(X)\) we denote the class of all orientations of \(X\). By Proposition 3.19, \[\begin{aligned} \sum_{T\in\mathcal{T}(X)}k(L(T))&=\sum_{T\in\mathcal{T}(X)}\left(\sum_{u\in\mathop{\mathrm{Si}}(T)\cup\mathop{\mathrm{So}}(T)}(d_{X}(u)-1)+1\right)\\ &=\sum_{T\in\mathcal{T}(X)}\sum_{u\in\mathop{\mathrm{Si}}(T)\cup\mathop{\mathrm{So}}(T)}(d_{X}(u)-1)+2^{n-1}. \end{aligned}\]
For every vertex \(u\in V(X)\) there are \(2\cdot 2^{n-1-d_{X}(u)}=2^{n-d_{X}(u)}\) orientations \(T\) of \(X\) in which \(u\) is a sink or a source. Therefore, \[\sum_{T\in\mathcal{T}(X)}k(L(T))=\sum_{u\in V(X)}(d_{X}(u)-1)2^{n-d_{X}(u)}+2^{n-1}.\]
This means that the average number of weak components in \(L(T)\) among orientations \(T\) of \(X\) equals \[\begin{aligned} \frac{1}{|\mathcal{T}(X)|}\sum_{T\in\mathcal{T}(X)}k(L(T))&=\frac{1}{2^{n-1}}\left(\sum_{u\in V(X)}(d_{X}(u)-1)2^{n-d_{X}(u)}+2^{n-1}\right)\\ &=\sum_{{\substack{u\in V(X)}}}\frac{d_{X}(u)-1}{2^{d_{X}(u)-1}}+1. \end{aligned}\] ◻
Also, note that Corollary 3.20 implies that for a given tree \(X\) among its orientations \(T\), the line digraph \(L(T)\) on average has at most \(\frac{1}{2}(|V(X)|-|\mathop{\mathrm{Leaf}}(X)|)+1\) weak components.
In what follows, we are going to provide an algorithm that for a given polytree \(T\) constructs its induced subgraphs that become weak components in \(L(T)\).
Polytree \(T\) Set \(\mathcal{C}\) of induced subgraphs of \(T\) which are mapped to different weak components when applying line digraph operator
\(\mathcal{C} \leftarrow \emptyset\). \(A_{out} \leftarrow\) the set of out-arcs from sources of \(T\). \((a, b) \leftarrow\) an out-arc from \(A_{out}\). \(S \leftarrow T[\{a, b\}]\). \(S_{prev} \leftarrow\) null digraph. \(S_{prev} \leftarrow S\). \(S \leftarrow T[\{\alpha \in A(T)| \alpha\ \text{is connected with some arc from}\ S\}]\). \(\mathcal{C} \leftarrow \mathcal{C} \cup \{S\}\). \(A_{out} \leftarrow A_{out} \backslash A(S)\).
Remark 3.21. After every iteration of the while cycle (lines 7–10) we either have added new arcs to \(S\), or \(S = S_{prev}\) and we terminate. Since the total number of arcs in \(T\) is finite, this process cannot continue indefinitely.
As for the main while cycle (lines 3–13), every iteration of it begins with extracting an arc from \(A_{out}\) and ends with deleting some arcs from \(A_{out}\), including the one extracted. Thus the algorithm performs at most as many iterations as there are elements of \(A_{out}\), which proves its termination.
Example 3.22. Consider the polytree \(T\) from Figure 8. Let us apply Algorithm 1 to it.
Initially \(A_{out}\) contains four arcs: \(a\), \(d\), \(h\), \(i\). We shall pick arc \(a\). Hence, \(S = T[a]\) as we enter the inner while cycle. On each iteration of it, we add all the arcs connected with any of the arcs already in \(S\), obtaining: \(A(S) = \{a\} \rightarrow \{a, b, c, e, f\} \rightarrow \{a, b, c, d, e, f, g, h\}\). There is no arc we can add to that, so the inner while cycle terminates and we add the newly built subgraph to \(\mathcal{C}\).
Now \(A_{out}\) contains a single arc \(i\). The inner cycle shall go \(A(S) = \{i\} \rightarrow \{i, j, k\}\). After that we add \(S\) to \(\mathcal{C}\). This way we divided \(T\) into two subgraphs which are mapped to different weak components of \(L(T)\).
Lemma 3.23. Every subgraph \(C_{1}\in\mathcal{C}\) generated by Algorithm 1 is weak.
Proof. As shown in remark above, \(C_1\) is generated by accumulating arcs through consecutive iterations of the inner while cycle. Line \(9\) of the algorithm implies that for all \(k > 1\) an arc generated on iteration \(k\) is connected to some arc generated on step \(k – 1\). Given that on step \(1\) the cycle \(C_{1}\) is connected, the fact that after terminating the inner while cycle \(C_{1}\) is still weak follows easily by induction. ◻
The next theorem justifies Algorithm 1.
Theorem 3.24. Let \(C_1, C_2, \dots, C_n\) be subgraphs obtained by applying Algorithm 1 to the polytree \(T\). Then the next statements hold:
1. \(L(C_k)\) is a weak digraph for all \(k \in [1, n]\).
2. \(L(C_k\cup\{\alpha\})\) is not weak, for all \(k \in [1, n]\) and for every \(\alpha \in A(T) \backslash A(C_k)\).
3. \(A(C_1)\sqcup A(C_2)\sqcup\dots\sqcup A(C_n) = A(T)\).
Proof. 1. Statement \(\textit{1}\) can be proved by induction similar to the one used in Lemma 3.23. On the first iteration, \(C_{k}\) consists of a single arc, therefore clearly \(L(C_{k})\) is weak. Let then \(\alpha\) be an arc added to \(C_{k}\) on iteration \(i \geq 2\). There exists an arc \(\beta\) already in \(C_{k}\) such that \(\alpha\) is connected with \(\beta\) by a dipath \(P\). But \(L(P)\) is also a dipath, \(\alpha\) and \(\beta\) being its end-vertices. This means that they belong to the same weak component in \(L(C_{k})\). However, by induction assumption there has only been one weak component so far; thus \(L(C_{k})\) is weak.
2. If \(\alpha \not \in A(C_k)\), then \(\alpha\) isn’t connected with any arc from \(C_k\) (if it were connected with an arc \(\beta\), it would be generated on the next iteration after \(\beta\) and therefore belong to \(C_k\)), and so the vertex of \(L(T)\) associated with it will lie in different weak component than \(L(C_k)\). This completes the proof of statement \(\textit{2}\).
3. Finally, we shall prove that all sets \(A(C_i)\) are pairwise disjoint. Let \(A(C_1) \cap A(C_2) = S\). Lemma 3.23 implies that \(C_1\) is weak, thus there exists \(a \in V(C_1)\) such that \(a\) is incident with arcs \(\alpha \in S\) and \(\beta \in C_1 \backslash S\). From statement \(\textit{1}\) together with Proposition 3.8 we have that \(a\) is not a source nor a sink, hence without loss of generality, we assume \(a\) is incident from \(\alpha\) to \(\beta\). This implies that there is a dipath containing both \(\alpha\) and \(\beta\), namely, \(\alpha – \beta\) is a dipath. Thus, since \(\alpha\) is in \(C_2\) (\(S \subset A(C_2)\)), \(\beta \in C_2\) as well – it will be generated on the next iteration after \(\alpha\). A contradiction, which implies \(A(C_1) \cap A(C_2) = \emptyset\).
To prove statement \(\textit{3}\) we still need to show that for all arcs \(\alpha \in A(T)\) there is \(k \in \mathbb{N}\) with \(\alpha \in A(C_k)\). If \(\alpha\) is an out-arc from a source, then the algorithm doesn’t terminate until it is marked as visited, that is, it belongs to some \(C_k\). Otherwise, we assert that \(\alpha\) is connected by a dipath to some out-arc from a source: as \(\alpha\) is not an out-arc from a source, there is an arc \(\beta_1\) which is adjacent to \(\alpha\). Now we have that either \(\beta_1\) is an out-arc from a source, or there is an arc \(\beta_2\) adjacent to \(\beta_1\). The process terminates when we reach an arc \(\beta_m\) that is an out-arc from a source (it cannot continue indefinitely, since the total number of arcs in \(T\) is finite). Thus \(\alpha\) will be generated no later than on the next iteration after \(\beta_m\). ◻
The authors express their gratitude to Y.-L. Dekhtiar, who carefully read the draft version of the paper and made suggestions that helped improve the clarity of its presentation.