We present a theorem which characterizes the class of line graphs of directed graphs. The characterization is an analogue of both the characterization of line graphs by Krausz (1943) and of directed line graphs of directed graphs by Harary and Norman (1960). Our characterization simplifies greatly in the case that the graph is bipartite. This and another result which we present draws attention to the special case of bipartite line graphs of directed graphs. As a result we explore the problem of finding the complete list of forbidden subgraphs for the class of bipartite line graphs of directed graphs. It appears, however, that this problem is extremely difficult. We do find two infinite families of forbidden subgraphs as well as several other illustrative examples.
Theorem 1.1 is a result of Krausz [8] which characterizes the class of line graphs. Beineke [2] uses Theorem 1.1 to find the complete list of forbidden subgraphs for the class of line graphs. There are nine of them.
Theorem 1.1(Krausz [8]).A graph \(G\) is the line graph of another graph if and only if \(E(G)\) can be partitioned into edge sets of cliques so that each vertex of \(G\) is in at most two of these cliques.
Let \(D\) be a directed simple graph (that is, a directed graph whose underlying graph is simple). All directed graphs in this paper are assumed to be directed simple graphs unless otherwise specified. The directed line graph of \(D\), denoted by \(\vec{\mathcal L}(D)\), is the directed graph whose vertex set is \(E(D)\) where \(((a,b),(c,d))\) is a directed edge in \(\vec{\mathcal L}(D)\) when \(b=c\).
A monotone directed biclique is a directed graph whose underlying graph is \(K_{a,b}\) for \(a,b\geq1\) in which the edges all have their tails (and therefore heads) in the same partite set.
Theorem 1.2(Harary and Norman [6]).A directed graph \(D\) is the directed line graph of a simple directed graph if and only if the edge set of \(D\) can be partitioned into monotone directed bicliques so that each vertex is in at most one tail set and at most one head set of these bicliques.
The line graph of a directed graph \(D\) is the underlying graph of \(\vec{\mathcal L}(D)\). Directed line graphs of directed graphs were introduced by Harary and Norman in [6] in 1960 and have since been a topic of active investigation. Bagga and Beineke have recently published a survey on the topic [1] as well as a book [3] which contains the topic. In contrast to this, line graphs of directed graphs were newly introduced in 2024 by the current authors [9] as a natural example of a hereditary class of graphs. Given Theorems 1.1 and 1.2, it is natural to seek a characterization of line graphs of directed graphs based on bicliques.
A biclique is a complete bipartite graph. Let \(G\) be a graph whose edge set decomposes into a disjoint union of edge sets of bicliques such that: no vertex is in more than two bicliques and no two bicliques intersect in more than vertex. Let \(\mathcal B\) be the set of these biclique subgraphs of \(G\). Evidently there is a simple graph \(\mathcal B(G)\) whose vertex set is \(\mathcal B\) where \(B_1,B_2\in\mathcal B\) are adjacent by an edge in \(\mathcal B(G)\) when \(B_1\) and \(B_2\) intersect in a vertex. Note that the neighbors of a vertex \(B\) in the graph \(\mathcal B(G)\) partition into two types: bicliques intersecting \(B\) in one partite set and bicliques intersecting \(B\) in its other partite set. Now if \(C\) is a cycle in \(\mathcal B(G)\) containing vertex \(B\), then we say that \(B\) is a switch vertex relative to cycle \(C\) when the neighbors of \(B\) on \(C\) intersect \(B\) in different partite sets. In Figure 1 we show six bicliques which form a cycle in \(\mathcal B(G)\) with four switch vertices.
Theorem 1.3 is our characterization of line graphs of directed graphs in terms of bicliques. Condition (2) of the theorem is necessary because of the simplicity of the underlying graph of the directed graph. Compared with Theorem 1.2, the increased complexity of condition (3) is expected due to the increased loss of information in the transformation from \(\vec{\mathcal L}(D)\) to \(\mathcal L(D)\). The proof of Theorem 1.3 is in Section 2.
Theorem 1.3. A graph \(G\) is of the form \(\mathcal L(D)\) for some directed simple graph \(D\) if and only if \(E(G)\) can be partitioned into edge sets of bicliques such that
(1) every vertex is in at most two bicliques,
(2) no two bicliques intersect in more than a single vertex, and
(3) if \(C\) is a cycle in \(\mathcal B(G)\), then the length of \(C\) and the number of switch vertices in \(C\) have the same parity.
Interestingly, Theorem 1.3 simplifies considerably to Corollary 1.4 when characterizing the class of bipartite line graphs of directed graphs.
Corollary 1.4. A bipartite graph \(G\) is of the form \(\mathcal L(D)\) for some directed simple graph \(D\) if and only if \(E(G)\) can be partitioned into edge sets of bicliques such that
(1) every vertex is in at most two bicliques and
(2) no two bicliques intersect in more than a single vertex.
Proof. If \(G=\mathcal L(D)\), then (1) and (2) follow from Theorem 1.4. If \(G\) satisfies (1) and (2), then property (3) of Theorem 1.4 follows from biparticity. Thus \(G=\mathcal L(D)\). ◻
Theorem 1.5 also draws attention to the bipartite case for line graphs of directed graphs. A vertex in a directed graph is singular when it is either a source or a sink. Note that if \(D_1\) and \(D_2\) are directed graphs which are related by identifying and splitting apart singular vertices of the same type, then \(\mathcal L(D_1)=\mathcal L(D_2)\). If \(D\) is a directed graph, then we use \(|D|\) to denote its underlying graph.
Theorem 1.5. Let \(D\) be a directed graph whose singular vertices all have degree 1. Then \(|D|\) is bipartite if and only if \(\mathcal L(D)\) is bipartite.
Proof. Suppose that \(|D|\) is bipartite. The possibilities for a directed graph \(D_n\) for which \(\mathcal L(D_n)\) is a cycle of length \(n\) were characterized in [9, Proposition 2.3-2.5]. If \(n\) is odd, then \(|D_n|\) always contains an odd cycle. Thus \(\mathcal L(D)\) is bipartite.
Suppose that \(\mathcal L(D)\) is bipartite but \(|D|\) is not. Let \(C\) be a subgraph of \(D\) such that \(|C|\) is an odd-length cycle of smallest possible length. If \(C\) is a directed cycle, then \(|C|\cong\mathcal L(C)\subseteq\mathcal L(D)\), a contradiction. If \(C\) is not a directed cycle, then it has an even number of singular vertices \(s^+_1,s^-_1,\ldots,s^+_t,s^-_t\) appearing in this order around \(C\) in which \(s^+_i\) is a sink and \(s^-_i\) is a source. Since \(|C|\) has smallest possible length among all odd-length cycles in \(|D|\), \(|C|\) has no chords. Thus for each \(i\in\{1,\ldots,t\}\), there are directed edges \((s^+_i,x_i)\) and \((y_i,s^-_i)\) in \(D\) because singular vertices in \(D\) all have degree 1. Let \(D'\) be the subgraph of \(D\) consisting of \(C\) along with these edges attached. Say that the length of \(C\) is \(2k+1\). Now \(\mathcal L(D')\subseteq\mathcal L(D)\) consists of a cycle of length \(2k+1+2t\) along with some chords depending on identifications among \(x_i\)’s and \(y_j\)’s. This contradicts the fact that \(\mathcal L(D)\) is bipartite. ◻
Line graphs and directed line graphs directed graphs are both hereditary classes; that is, closed under the operation of taking induced subgraphs. A hereditary class \(\mathcal H\) can thus be characterized by a list \(\mathcal L\) of graphs or directed graphs which are not contained in \(\mathcal H\) and are minimal in the induced subgraph ordering with respect to this property. Such graphs are succinctly referred to as the forbidden subgraphs for \(\mathcal H\). Theorem 1.6 gives the complete list of forbidden subgraphs for directed line graphs of directed graphs, there are only five.
Theorem 1.6(Bagga and Beineke [3, Theorem 11.5]).A directed graph \(D\) is the directed line graph of a directed graph if and only if \(D\) does not contain any one of the five directed graphs of Figure 2 as an induced subgraph.
In stark contrast to the simplicity of Theorem 1.6, the forbidden subgraphs for the class of line graphs of directed graphs contains multiple infinite classes of graphs, as the reader will see. The problem of finding all of the forbidden subgraphs seems to be very difficult. In our initial investigation into this topic [9] we looked at the intersection of the class of line graphs of acyclic directed graphs with the class of chordal bipartite graphs (see, for example, [4, 5, 7]). Our main results from [9] are as follows.
Proposition 1.7. If \(D\) is a directed tree, then \(\mathcal L(D)\) is chordal bipartite.
Theorem 1.8. If \(G\) is connected and chordal bipartite, then \(G\) is the line graph of an acyclic directed graph if and only if \(G\) is the line graph of a directed tree.
Theorem 1.9. Let \(\mathcal H\) be the intersection of the class of chordal bipartite graphs and the class of line graphs of acyclic directed graphs. The forbidden subgraphs for \(\mathcal H\) are \(H_1\), \(H_2\), and \(H_3\). (See Figure 3.)
Proposition 1.7 and Theorem 1.8 highlight an interesting and unexpected interaction between line graphs of directed graphs and the well-studied hereditary class of chordal bipartite graphs. Similarly, Theorem 1.5 and Corolloary 1.4 highlight an interesting interaction between line graphs of directed graphs and the hereditary class of bipartite graphs. Therefore, since the problem of finding the complete list of forbidden subgraphs for the full class of line graphs of directed graphs seems so difficult, it would make sense to consider the forbidden subgraphs for the class of bipartite line graphs of directed graphs. We find, however, that even this subproblem is quite difficult.
In Section 2 we prove Theorem 1.3. In Sections 3 through 6 we find and discuss some forbidden subgraphs for the class of bipartite line graphs of directed graphs which include two infinite classes. While we only proved the existence of these two, we believe that there are many more. These examples are meant to highlight the difficulty of the problem of finding all of these forbidden subgraphs.
A reasonable goal for a future investigation might be to try to find the list of forbidden subgraphs for the class of bipartite line graphs of acyclic directed graphs. (Confer Propositions 3.1 and 5.2.)
Proof. Suppose that \(G=\mathcal L(D)\) for some directed simple graph. For each vertex \(b\in D\), its incident edges form a biclique in \(G=\mathcal L(D)\). Certainly these bicliques in \(G\) satisfy (1). Furthermore, because the underlying graph of \(D\) is simple, the bicliques also satisfy (2). (It is worth noting that if the underlying graph of \(D\) is not simple, then (2) need not be satisfied.) Now, to show that Property (3) is satisfied, consider a cycle \(C\) in \(\mathcal B(G)\) with vertices corresponding to bicliques \(B_1,\ldots,B_n\) in \(G=\mathcal L(D)\) which again correspond to vertices in \(D\). By Property (1) the vertices \(B_i\cap B_{i+1}\) for \(i\in\{1,\ldots,n\}\) in \(G=\mathcal L(D)\) (subscript addition is modulo \(n\)) are distinct. The vertex \(B_i\cap B_{i+1}\) in \(G\) corresponds to either the directed edge \((B_i,B_{i+1})\) or \((B_{i+1},B_i)\) in \(D\). Thus vertices \(B_1,\ldots,B_n\) form a cycle \(C'\) in \(|D|\); furthermore, the direction on the edges of \(C'\) are such that vertex \(B_i\) is singular on \(C'\) if and only if \(B_i\) is not a switch vertex in \(G\) with respect to cycle \(C\). Since the number of singular vertices on a cycle of directed edges is even, the number of non-singular vertices and the length of the cycle have the same parity.
Conversely, assume that \(G\) is a graph satisfying (1)–(3). If \(G\) is not connected, then we can obtain a directed graph \(D\) for each connected component of \(G\) to satisfy our conclusion. Thus we may assume that \(G\) is connected. The fact that \(G\) is connected immediately implies that \(\mathcal B(G)\) is connected, because a path between any two vertices \(B_1\) and \(B_2\) of \(\mathcal B(G)\) is obtained by any path between vertices \(b_1\in B_1\) and \(b_2\in B_2\).
Again, let \(\mathcal B\) denote the vertices of \(\mathcal B(G)\) and let \(\mathcal S\) be the set of vertices of \(G\) which appear in only one member of \(\mathcal B\). Now every vertex of \(G\) appears in exactly two members of \(\mathcal B\cup\mathcal S\). This defines a graph whose vertex set is \(\mathcal B\cup\mathcal S\), call it \(D\). This graph \(D\) is actually \(\mathcal B(G)\) with the vertices in \(\mathcal S\) added as pendants connected to their associated member of \(\mathcal B\). Note that \(D\) is connected because \(\mathcal B(G)\) is connected.
Now we will orient the edges of \(D\). Let \(B_0\in\mathcal B\). Each vertex of the biclique \(B_0\) in \(G\) is in exactly one other element of \(\mathcal B\cup\mathcal S\) in \(G\). Thus the edges of \(D\) incident to vertex \(B_0\) represent the intersection of \(B_0\) with the other elements of \(\mathcal B\cup\mathcal S\). For elements \(\mathcal B\cup\mathcal S\) in one partite set of \(B_0\), orient the corresponding edges of \(D\) towards \(B_0\) and the edges of \(D\) corresponding to the other partite set of \(B_0\) away from \(B_0\).
Now let \(T_0\) be a spanning tree of \(D\) rooted at \(B_0\). For each vertex \(B\) of \(D\) there is a unique \(B_0B\)-path in \(T_0\), say \(B_0,B_1,\ldots, B_n=B\) are the vertices of this path. Given that the edges of \(D\) incident to \(B_i\) are already oriented, we now have a well-defined orientation on the edges of \(D\) incident to \(B_{i+1}\) according to the bipartition of the vertices of the biclique \(B_{i+1}\) in \(G\). This process yields a well defined orientation on the edges of \(T_0\) but not a priori for each edge of \(E(D)-E(T_0)\). Furthermore, note that for any path \(P\) of length 2 in \(T_0\), the directions on the two edges of \(P\) will be coherent if and only if the biclique of \(G\) corresponding to the center vertex of \(P\) intersects the two bicliques of \(G\) corresponding to the endpoints of \(P\) in different partite sets. So now consider any \(e\in E(D)-E(T_0)\) and its fundamental cycle \(C\) in \(T_0\cup e\). Say that \(b_1\) and \(b_2\) are the endpoints of \(e\). Because of this property on length-2 paths in \(T_0\) a vertex \(b\in V(C)-\{b_1,b_2\}\) is singular on the orientation of the path \(C-e\) if and only if the bicliques corresponding to its neighbors on \(C\) intersect the biclique \(b\) in \(G\) in the same partite set; that is, if and only if \(b\) is not a switch vertex of \(C\). If the number of switch vertices relative to \(C\) in \(V(C)-\{b_1,b_2\}\) has the same parity as the number of vertices in \(V(C)\), then either \(b_1\) and \(b_2\) are both switch or both non-switch relative to \(C\) (by Property (3)); furthermore, the first and last edges of \(C-e\) must be in the same direction along the path \(C-e\). Thus the direction of \(e\) is uniquely determined. This is similarly true when the number of switch vertices relative to \(C\) in \(V(C)-\{b_1,b_2\}\) has different parity as the number of vertices \(V(C)\). Thus we have a well defined orientation on the whole of \(D\). Now \(G=\mathcal L(D)\) because we have defined the directions on the edges according to the partite sets of each biclique. ◻
Given a bipartite graph \(G\), the problem of finding a directed bipartite graph \(D\) for which \(G=\mathcal L(D)\) is equivalent to the problem of partitioning \(E(G)\) so as to satisfy the conditions of Corollary 1.4. If such a partitioning exists, then some of the blocks are uniquely determined. Consider a biclique \(K_{m,n}\). We call the biclique fat if \(m\geq2\) and \(n\geq 3\). If \(1\in\{m,n\}\), then we call the biclique thin. The biclique \(K_{2,2}\) will be referred to as a quadrilateral.
Proposition 3.1([9, Proposition 2.4]).\(\mathcal L(D)\) is a quadrilateral if and only if \(D\) is a directed quadrilateral or \(|D|=K_{1,4}\) with two edges directed towards the central vertex and two edges directed away from the central vertex.
Proposition 3.2. If \(K_{m,n}\) is a fat biclique, then \(\mathcal L(D)=K_{m,n}\) if and only if \(|D|=K_{1,m+n}\) with \(m\) edges directed towards the central vertex and \(n\) edges directed away from the central vertex.
Proof. Consider \(\mathcal L(D)=K_{m,n}\) in which \(m\geq n\) and say that \(e\in E(D)\) corresponds to a vertex from the \(m\)-vertex partite set. If \(K_{m,n}-e\) is \(K_{2,2}\), then by Proposition 3.1, \(D-e\) is either a directed quadrilateral or a directed \(K_{1,4}\) with two edges oriented towards the central vertex and two oriented away from the central vertex. Evidently, however, there is no way to add \(e\) to a directed quadrilateral so that \(\mathcal L(D)=K_{3,2}\) and the only way to add \(e\) is so that \(D\) is a directed \(K_{1,5}\) as stated in the proposition. If \(K_{m,n}-e\) is not \(K_{2,2}\), then \(K_{m,n}-e\) is a thick biclique. Inductively, \(D-e\) is a directed \(K_{1,m+n-1}\) as given in the statement of the proposition. Now the only way to add \(e\) so that \(\mathcal L(D)=K_{m,n}\) is so that \(D\) is a directed \(K_{1,m+n}\). ◻
Proposition 3.3. The graph \(K_{3,3}-e\) is a forbidden subgraph for the class of line graphs of directed graphs.
Proof. If we delete a degree-2 vertex, call it \(v\), from \(K_{3,3}-e\) we obtain \(K_{2,3}\). By Proposition 3.2, \(\mathcal L(D)\cong K_{2,3}\) if and only if \(|D|\cong K_{1,5}\) with two edges in one direction and three in the other. Now vertex \(v\) is adjacent to two of the three degree-2 vertices of \(K_{2,3}\). The directed edges of \(D\) representing these degree-2 vertices are in the same direction along the star \(|D|\cong K_{1,5}\). There is no way to add a new directed edge to obtain \(K_{3,3}-e\).
To show minimality, consider a trivalent vertex \(v\) of \(K_{3,3}-e\) (we already confirmed for 2-valent). Up to symmetry there is only one possibility for \(v\). Deleting \(v\) results in a quadrilateral with a pendant vertex attached. Clearly this the line graph of a directed graph. ◻
Since \(K_{3,3}-e\) is now known to be a forbidden subgraph for line graphs of directed graphs, one can consider the hereditary class, call it \(\mathcal H\), of bipartite graphs without an induced \(K_{3,3}-e\) which properly contains the class of bipartite line graphs of directed graphs. Proposition 3.4 describes an interesting property of graphs in \(\mathcal H\). If \(B\) is a biclique in a bipartite graph \(G\) and \(v\) is a vertex of \(G\) with \(v\notin B\), then we say that \(v\) extends \(B\) when \(B\cup v\) induces a larger biclique.
Proposition 3.4. Let \(G\) be a bipartite graph not containing an induced \(K_{3,3}-e\). If \(B\cong K_{m,n}\) is a biclique in \(G\) with \(m,n\geq2\) and \(v\) is a vertex of \(G\) such that \(v\notin B\), then either \(v\) is adjacent to at most one vertex in \(B\) or \(v\) extends \(B\).
Proof. Suppose that \(B\cong K_{m,n}\) is a biclique with \(m,n\geq 2\). If \(m=n=2\), then the conclusion is trivially satisfied. So suppose that \(B\) is thick and denote its partite sets by \(P\) and \(Q\). If By way of contradiction say \(v\) is a vertex in \(G\) which is adjacent to at least two vertices in \(P\), say \(p_1\) and \(p_2\), but \(v\) is not adjacent to \(p_3\in P\). In this case \(p_1,p_2,p_3,v\) along with any two vertices in \(Q\) induce \(K_{3,3}-e\), a contradiction. ◻
Theorem 1.3(1) suggests that there should be forbidden subgraphs which have a vertex incident to too many bicliques. Two such graphs are given in Proposition 4.1.
Proposition 4.1. The two graph of Figure 4 are forbidden subgraphs for the class of line graphs of directed graphs.
Proof. Let \(H\) be either one of the graphs in Figure 4 and \(w\) the degree-1 vertex of \(H\). By Propositions 3.2 and 3.1, the only directed graphs \(D\) up to reversal and identification of singular vertices which represent \(H-w\) are shown either on the left or right of Figure 5.
From here there is no way to add another edge to \(D\) so that \(\mathcal L(D)=H\).
It remains to confirm the minimality of the two graphs in Figure 4. Let \(H\) be either of the graphs in Figure 4 and let \(u\) a vertex of \(H\). Evidently \(H-u\cong H_3\) of Figure 3 or \(H-u\) contains none of the graphs of Figure 3 as an induced subgraph. In the latter case, \(H-u\) is the line graph of a directed tree. In the former case, let \(D\) consists of two directed quadrilaterals overlapping in exactly one edge along with a pendant edge attached to one vertex of this intersection and directed coherently with that edge. Clearly \(H-u=\mathcal L(D)\). ◻
Given a graph \(G\), a major difficulty in determining possible directed graphs \(D\) for which \(G=\mathcal L(D)\) is the fact that a quadrilateral is a biclique but has two possible representations as a directed graph (Proposition 3.1). In this section we present two infinite classes of forbidden subgraphs using long strings of quadrilaterals. One class also contains thick bicliques and the other class does not contain thick bicliques.
A string of \(n\) quadrilaterals consists of quadrilaterals \(Q_1,\ldots,Q_n\) for which each \(Q_i\cap Q_{i+1}\) is a single vertex for each \(i\in\{1,\ldots,n-1\}\) and there are no other vertices of intersection among the quadrilaterals. A string of \(n\) quadrilaterals is straight when for each \(i\in\{2,\ldots,n-1\}\), the two vertices \(Q_{i-1}\cap Q_{i}\) and \(Q_i\cap Q_{i+1}\) are not adjacent on \(Q_i\).
Proposition 5.1. If \(G\) is a string of \(n\) quadrilaterals \(Q_1,\ldots,Q_n\) and \(G=\mathcal L(D)\), then either each \(Q_i\) is represented in \(D\) by a directed square or each \(Q_i\) is represented in \(D\) by a directed \(K_{1,4}\).
Proof. The reader can check the result for \(n=2\). Now if \(Q_i\cup Q_{i+1}\) is represented by two \(K_{1,4}\)’s or two directed squares, then the result for \(n=2\) implies that \(Q_{i+1}\cup Q_{i+2}\) is represented in the same way. The result follows. ◻
A domino is a graph consisting of two squares which intersect along a single edge. (See Figure 6.) Notice that if \(\mathcal L(D)\) is a domino, then either one or both squares of \(\mathcal L(D)\) are represented by directed squares in \(D\); that is, it cannot be that both squares in \(\mathcal L(D)\) are represented by \(K_{1,4}\)’s in \(D\).
Proposition 5.2. If \(\mathcal L(D)\) is a domino, then \(D\) is isomorphic to one of the two directed graphs in Figure 6 up to reversal.
Proof of Proposition 5.2. It cannot be that both squares of \(\mathcal L(D)\) are represented by directed stars because the two directed stars would have to share two edges which would mean that the two stars are one directed star. A single directed star produces a biclique and a domino is not a biclique. Thus the two squares of \(\mathcal L(D)\) are both represented by directed squares or one is a directed square and the other by a directed star. The only possibilities are those shown in Figure 6. ◻
Proposition 5.3. If \(G\) is obtained from two vertex-disjoint copies of \(K_{2,3}\) along with a string of \(n\geq2\) quadrilaterals where the first quadrilateral intersects one \(K_{2,3}\) in a single vertex and the last quadrilateral intersects the other \(K_{2,3}\) in an edge, then \(G\) is bipartite and \(G\neq\mathcal L(D)\) for any directed graph \(D\).
Proof. Suppose that \(G=\mathcal L(D)\). The induced quadrilaterals in the \(K_{2,3}\) must be represented by directed \(K_{1,4}\)’s in \(D\). Now if \(Q\) is a quadrilateral in the string, Propositions 5.1 and 5.2 imply that there is no possible way to represent \(Q\) in \(D\), a contradiction. ◻
We conjecture that any graph described in Proposition 5.3 is a forbidden subgraph for \(\mathcal L(D)\). It is only left to prove the minimality of any such graph. To cut down on casework we will instead just prove the minimality for the infinite class of graphs with straight strings shown in Figure 7.
Proposition 5.4. Any graph of the form shown in Figure 7 is a forbidden subgraph for \(\mathcal L(D)\).
Proof. If \(G\) is as shown in Figure 7, then \(G\) is not a line graph of a directed graph by Proposition 5.3. We need only prove minimality.
Neither \(G-6\) nor \(G-7\) contains a graph from Figure 3, so both \(G-6\) and \(G-7\) are line graphs of directed trees by Theorem 1.9.
The graph \(G-5=\mathcal L(D)\) for \(D\) which consists of the following: a directed \(K_{1,5}\) (which represents the \(K_{2,3}\)-subgraph of \(G-5\)) followed by a sequence of \(K_{1,4}\)’s (which represent the quadrilaterals in the string) and ending with a directed square on the last \(K_{1,4}\) (which represents the second quadrilateral in the domino of \(G-5\).).
The graph \(G-2=\mathcal L(D)\) for \(D\) which consists of the following: a directed \(K_{1,5}\) (which represents the \(K_{2,3}\)-subgraph of \(G-2\)) followed by a sequence of directed squares which represent the quadrilaterals in the straight string.
The graph \(G-1=\mathcal L(D)\) for \(D\) which consists of the following: a directed \(K_{1,5}\) (which represents the \(K_{2,3}\)-subgraph of \(G-2\)) followed by a sequence of directed squares (which represent the quadrilaterals in the straight string) and ending with three pendant edges in the same direction on a vertex in the last quadrilateral.
If \(v\) is a degree-4 vertex along the straight string in \(G\) (e.g., vertex 4 in Figure 7), then the left-hand connected component of \(G-v\) is the line graph of a directed tree by Theorem 1.9 and the right-hand connected component of \(G-v\) is the line graph of a directed graph as constructed for \(G-1\).
Let \(v\) be a degree-2 vertex along the straight string in \(G\) (e.g., vertex 3 in Figure 7) and say that \(v'\) is the other degree-2 vertex of \(G\) on the same quadrilateral as \(v\). There are directed graphs \(D_1\) and \(D_2\) which represent the two connected components of \(G-v\). Now an single directed edge can be added which connects the final directed \(K_{1,4}\) of \(D_1\) and the final directed square of \(D_2\) to obtain a directed graph \(D\) which represents \(G-v\). ◻
Let \(S\) be a string of \(n\geq 2\) quadrilaterals. A clasp on \(S\) consists of a degree-3 vertex \(x\) adjacent to one degree-2 vertex on each of the first and last quadrilaterals of \(S\) along with a new degree-1 vertex \(y\) adjacent to \(x\), see Figure 8.
Proposition 5.5. If \(G\) is a string along with a clasp, \(\mathcal L(D)=G\), and every singular vertex of \(D\) has degree 1 in \(|D|\), then every quadrilateral of \(G\) is represented in \(D\) by a directed \(K_{1,4}\).
Proof. Let \(S\) be the string of quadrilaterals in \(G\). Proposition 5.1 implies that each \(Q_i\) is represented in \(D-\{x,y\}\) by a directed square or each \(Q_i\) is represented by a directed \(K_{1,4}\). Assume by way of contradiction that the quadrilaterals of \(S\) are represented by directed squares in \(D-\{x,y\}\). Now directed edge \(x\) in \(D\) must attach to a degree-2 vertex of each of the first and last directed squares of \(D\), see Figure 9.
Because \(x\) is adjacent to only two vertices on the string of quadrilaterals, directed edge \(x\) cannot be incident to the vertices of higher degree on the chain of directed squares. Now there is no way to add directed edge \(y\) incident to \(x\) which results in a degree-1 vertex of \(\mathcal L(D)\), a contradiction. ◻
Proposition 5.6. If \(S\) is a straight string of quadrilaterals of length \(2k\) and \(D\) is a domino and \(G\) is graph obtained from \(S\) and \(D\) by identifying as indicated in Figure 10, then \(G\) is bipartite, \(G\) contains no fat biclique, and \(G\) is a forbidden subgraph for the class of bipartite line graphs of directed graphs.
Proof of Proposition 5.6. Suppose by way of contradiction that \(G=\mathcal L(D)\). A string with a clasp is an induced subgraph of \(G\), so Propositions 5.1 and 5.5 imply that all quadrilaterals in \(G\) are represented in \(D\) by \(K_{1,4}\)’s; however, this contradicts Proposition 5.2.
We now check minimality. For vertex 1 in Figure 10, we construct a directed graph representing \(G-1\) as follows. Represent the string of quadrilaterals with a chain of \(K_{1,4}\)’s in which all singular vertices have degree 1. Now the edges in this chain of \(K_{1,4}\)’s which represents the fist and last vertices of the string of quadrilaterals can be connected via a coherent of directed edges of length 3 in order to represent the path connecting the ends of the string. Directed graphs representing \(G-2\), \(G-4\), and \(G-5\) are shown in Figure 11.
The graph \(G-3\) is a string of quadrilaterals with some pendant edges attached to the first and last quadrilaterals. A directed graph representing \(G-3\) is again constructed starting with a chain of \(K_{1,4}\)’s and adding pendant edges to the first and last \(K_{1,4}\) as needed. ◻
Alas, even bipartite graphs without quadrilaterals still contain forbidden subgraphs for the class of bipartite line graphs of directed graphs. We did not find an infinite family of forbidden subgraphs of girth at least 6, but the example in Proposition 6.1 was an obvious first guess among cubic bipartite graphs of girth at least 6.
Proposition 6.1. The Heawood graph minus any one vertex (the first graph in Figure 12) is a forbidden subgraph for the class of bipartite line graphs of directed graphs.
Proof. Let \(H\) be the Heawood graph minus any one vertex. To show that \(H\neq\mathcal L(D)\) for any \(D\), assume by way of contradiction that \(E(H)\) has a decomposition into bicliques as described in Corollary 1.4. Up to rotational symmetry, the central vertex of \(H\) has the two edges shown in Figure 12 in biclique 1. From here the assignment of bicliques 2 though 5 are forced. This leaves no possibility for a biclique on the edge indicated, a contradiction.
Now a biclique decomposition for the edges of each vertex-deleted subgraph of \(H\) are shown in Figure 12. Thus each vertex-deleted subgraph of \(H\) is a line graph of a directed graph by Corollary 1.4. ◻
Author Viady Sivaraman is partially supported by the Simons Foundation Travel Support for Mathematicians – Award No. 855469.