# Factorizability Dependency on Directed Graphs

İsmail Alperen Öğüt

► To cite this version:

İsmail Alperen Öğüt. Factorizability Dependency on Directed Graphs. 2024. hal-04573094v2

HAL Id: hal-04573094

https://hal.science/hal-04573094v2

Preprint submitted on 15 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_1.png" /></figure>

HAL
open science

# Factorizability Dependency on Directed Graphs

İsmail Alperen Öğüt

► To cite this version:

İsmail Alperen Öğüt. Factorizability Dependency on Directed Graphs. 2024. hal-04573094v2

HAL Id: hal-04573094

https://hal.science/hal-04573094v2

Preprint submitted on 15 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Factorizability Dependency on Directed Graphs

İsmail Alperen Öğüt*

Department of Electronics and Automation
Ankara University
06935 Sincan, Ankara, Turkey

May 15, 2024

## Abstract

Given a directed graph $D$, we introduce its factorizability dependency graph $FD(D)$ which encodes the information whether a pair of edges can both be omitted while maintaining the original reachability relations. We prove that $FD(D)$ is triangle-free and its chromatic number relative to 2 is a lower bound for directed biclique covering number of $D$. As a generalization, we introduce the weak factorizability dependency $WFD(D)$ graph which captures the edges that become dependant on each other in terms of factorizability in an equivalent subgraph $S$ of $D$. We prove that these pairs of edges together with the set $D \times S$ form a clique of $WFD(D)$. Lastly, we study the lattice of equivalent subgraphs $\mathcal{L}_D$ of $D$ and under a certain assumption, explore a connection between the longest cycle length of $FD(D)$ and the realizability of the lattice $M_3$ as a sublattice of $\mathcal{L}_D$.

2010 Mathematics Subject Classification: Primary 05C20, Secondary 05C70.

Keywords: Directed graph, equivalent subgraph, directed biclique covering, transitive reduction, lattice, independent domination

## 1 Introduction

All graphs are assumed to be finite, contain no loops. Let $D$ be a directed graph. An *equivalent subgraph* $E$ of $D$ is a subgraph which preserves the reachability relations of $D$. If no proper subgraph of $E$ has this property, then we call $E$ a *minimal equivalent subgraph* of $D$. Finding an algorithm to obtain a minimal equivalent subgraph with least number of edges, that is, a *minimum equivalent subgraph* is an important problem that has been considered long time ago in [6]. A related notion that is studied in [2] is the *transitive reduction* of a directed graph where the aim is still to find a graph with the same reachability relations as $D$ without requiring it to

<footnote>*e-mail: iaogut@ankara.edu.tr</footnote>
# Factorizability Dependency on Directed Graphs

İsmail Alperen Öğüt*

Department of Electronics and Automation
Ankara University
06935 Sincan, Ankara, Turkey

May 15, 2024

## Abstract

Given a directed graph $D$, we introduce its factorizability dependency graph $FD(D)$ which encodes the information whether a pair of edges can both be omitted while maintaining the original reachability relations. We prove that $FD(D)$ is triangle-free and its chromatic number relative to 2 is a lower bound for directed biclique covering number of $D$. As a generalization, we introduce the weak factorizability dependency $WFD(D)$ graph which captures the edges that become dependant on each other in terms of factorizability in an equivalent subgraph $S$ of $D$. We prove that these pairs of edges together with the set $D \times S$ form a clique of $WFD(D)$. Lastly, we study the lattice of equivalent subgraphs $\mathcal{L}_D$ of $D$ and under a certain assumption, explore a connection between the longest cycle length of $FD(D)$ and the realizability of the lattice $M_3$ as a sublattice of $\mathcal{L}_D$.

2010 Mathematics Subject Classification: Primary 05C20, Secondary 05C70.

Keywords: Directed graph, equivalent subgraph, directed biclique covering, transitive reduction, lattice, independent domination

## 1 Introduction

All graphs are assumed to be finite, contain no loops. Let $D$ be a directed graph. An *equivalent subgraph* $E$ of $D$ is a subgraph which preserves the reachability relations of $D$. If no proper subgraph of $E$ has this property, then we call $E$ a *minimal equivalent subgraph* of $D$. Finding an algorithm to obtain a minimal equivalent subgraph with least number of edges, that is, a *minimum equivalent subgraph* is an important problem that has been considered long time ago in [6]. A related notion that is studied in [2] is the *transitive reduction* of a directed graph where the aim is still to find a graph with the same reachability relations as $D$ without requiring it to

<footnote>*e-mail: iaogut@ankara.edu.tr</footnote>
be a subgraph. A modern treatment with the focus on the reachability preserver of a graph and its demand pairs can be found in [1].

In this paper, we aim to explore the structural restrictions a graph poses on its equivalent subgraphs. For this, we introduce the notion of *factorizability dependency*, which is a relation that states whether the removal of one edge affects the removability of the other in terms of maintaining the original reachability relations. To encapsulate this, we define the *factorizability dependency graph* $\mathcal{FD}(D)$ of $D$. It turns out that the factorizability dependency is an anti-transitive symmetric relation, so $\mathcal{FD}(D)$ is triangle-free.

A *directed biclique* is a complete directed bipartite graph where all edges are oriented from one part to the other. A crucial invariant of $D$ to which $\mathcal{FD}(D)$ relates is the *minimum directed biclique covering* of $D$, i.e., the minimum number of directed biclique subgraphs required such that every edge of $D$ is contained in at least one of them. An extensive survey and study of this problem can be found in [5]. For a more recent treatment and its variations for the case of undirected graphs see [4]. We will prove that the minimum directed biclique covering of a directed graph is bounded below by $\chi(2, \mathcal{FD}(D))$, i.e., the chromatic number of $\mathcal{FD}(D)$ relative to 2.

In the process of removing edges, it is possible for two edges that were not initially so to become dependant on each other in terms of factorizability. To capture this condition and generalize $\mathcal{FD}(D)$ we define the *weak factorizability dependency graph* $\mathcal{WFD}(D)$ of $D$. The crucial outcome of studying this structure is that the edges one has to remove for a factorizability dependency relation to emerge, together with the edges that form this relation are all related to each other in terms of weak factorizability, thus form a clique of $\mathcal{WFD}(D)$.

In the last section, we study the lattice $S_D$ of equivalent subgraphs of $D$. Alternatively, $S_D$ can be seen as the lattice of opposite poset of independent sets of $\mathcal{FD}(D)$. In general, the graph $\mathcal{FD}(D)$ does not reveal much about $S_D$. However, under the assumption $\mathcal{WFD}(D) \cong \mathcal{FD}(D)$ as we shall show, an interesting connection appears; the length of the longest cycle in $\mathcal{FD}(D)$ controls the realizability of $M_3$ as a sublattice of $S_D$.

## 2 The graph $\mathcal{FD}(D)$

Given a directed graph $D$, let $V(D)$ and $E(D)$ denote its set of vertices and edges, respectively. In this section we will introduce the relation $\sim$ on $E(D)$. Given finite sets $A, B$ such that $A \supseteq E(D) \subseteq B$, the graph $D$ can canonically be realized as a subset of $A \times B$. To utilize this realization we will identify $D$ with its edge set $E(D)$ and use the term edge for the elements of $D$.

Given an edge $u \in D$, we let $u = (u_i, u_t)$ denote the *initial* and *terminal* vertices of $u$. A *walk* $W$ for $u$ in $D$ is an ordered subset $((u_i, x_1), (x_1, x_2), \cdots, (x_{n-1}, u_t)) \subseteq D$ such that $n \ge 2$. Letting $x_0 = u_i, x_n = u_t$ we say $W$ is a *path for u in D* if no proper subset of $W$ is a walk for $u$, that is; for all $0 \le j, k \le n$, we have $x_j = x_k$ if and only if $j = k$. Thus in a path every vertex and edge is visited at most once. The set of all paths for $u$ in $D$ will be denoted by $\mathcal{P}_D(u)$. We shall omit writing the set in which a path resides and drop the subscript $D$ whenever it is clear from the context. An edge is called *factorizable* if there exists a path for it.

Given a path $P$ and vertices $x, y$ such that $x$ is visited before $y$ in $P$, let $Q \subseteq P$ be the unique
be a subgraph. A modern treatment with the focus on the reachability preserver of a graph and its demand pairs can be found in [1].

In this paper, we aim to explore the structural restrictions a graph poses on its equivalent subgraphs. For this, we introduce the notion of *factorizability dependency*, which is a relation that states whether the removal of one edge affects the removability of the other in terms of maintaining the original reachability relations. To encapsulate this, we define the *factorizability dependency graph* $\mathcal{FD}(D)$ of $D$. It turns out that the factorizability dependency is an anti-transitive symmetric relation, so $\mathcal{FD}(D)$ is triangle-free.

A *directed biclique* is a complete directed bipartite graph where all edges are oriented from one part to the other. A crucial invariant of $D$ to which $\mathcal{FD}(D)$ relates is the *minimum directed biclique covering* of $D$, i.e., the minimum number of directed biclique subgraphs required such that every edge of $D$ is contained in at least one of them. An extensive survey and study of this problem can be found in [5]. For a more recent treatment and its variations for the case of undirected graphs see [4]. We will prove that the minimum directed biclique covering of a directed graph is bounded below by $\chi(2, \mathcal{FD}(D))$, i.e., the chromatic number of $\mathcal{FD}(D)$ relative to 2.

In the process of removing edges, it is possible for two edges that were not initially so to become dependant on each other in terms of factorizability. To capture this condition and generalize $\mathcal{FD}(D)$ we define the *weak factorizability dependency graph* $\mathcal{WFD}(D)$ of $D$. The crucial outcome of studying this structure is that the edges one has to remove for a factorizability dependency relation to emerge, together with the edges that form this relation are all related to each other in terms of weak factorizability, thus form a clique of $\mathcal{WFD}(D)$.

In the last section, we study the lattice $S_D$ of equivalent subgraphs of $D$. Alternatively, $S_D$ can be seen as the lattice of opposite poset of independent sets of $\mathcal{FD}(D)$. In general, the graph $\mathcal{FD}(D)$ does not reveal much about $S_D$. However, under the assumption $\mathcal{WFD}(D) \cong \mathcal{FD}(D)$ as we shall show, an interesting connection appears; the length of the longest cycle in $\mathcal{FD}(D)$ controls the realizability of $M_3$ as a sublattice of $S_D$.

# 2 The graph $\mathcal{FD}(D)$

Given a directed graph $D$, let $V(D)$ and $E(D)$ denote its set of vertices and edges, respectively. In this section we will introduce the relation $\sim$ on $E(D)$. Given finite sets $A, B$ such that $A \supseteq E(D) \subseteq B$, the graph $D$ can canonically be realized as a subset of $A \times B$. To utilize this realization we will identify $D$ with its edge set $E(D)$ and use the term edge for the elements of $D$.

Given an edge $u \in D$, we let $u = (u_i, u_t)$ denote the *initial* and *terminal* vertices of $u$. A *walk* $W$ for $u$ in $D$ is an ordered subset $((u_i, x_1), (x_1, x_2), \cdots, (x_{n-1}, u_t)) \subseteq D$ such that $n \ge 2$. Letting $x_0 = u_i, x_n = u_t$ we say $W$ is a *path for u in D* if no proper subset of $W$ is a walk for $u$, that is; for all $0 \le j, k \le n$, we have $x_j = x_k$ if and only if $j = k$. Thus in a path every vertex and edge is visited at most once. The set of all paths for $u$ in $D$ will be denoted by $\mathcal{P}_D(u)$. We shall omit writing the set in which a path resides and drop the subscript $D$ whenever it is clear from the context. An edge is called *factorizable* if there exists a path for it.

Given a path $P$ and vertices $x, y$ such that $x$ is visited before $y$ in $P$, let $Q \subseteq P$ be the unique
path for $(x, y)$ in $P$. Define the set $P(x, y)$ as follows:

$$P(x, y) = \begin{cases} Q & \text{if } (x, y) \notin P \\ (x, y) & \text{otherwise.} \end{cases}$$

**Lemma 2.1.** Let $D$ be a directed graph, $(x_0, x_n) \in D$ and $P_1$ be a path for $(x_0, x_n)$ in $D$. Let $(y_0, y_m) \in P_1$ and suppose that there exists a path $P_2$ for $(y_0, y_m)$ in $D$ satisfying any of the following conditions:

(i) $(x_0, x_n) \notin P_2$

(ii) $P_2 \cap P_1 \neq \emptyset$.

Then there exists a path $P$ for $(x_0, x_n)$ in $U$ such that $(y_0, y_m) \notin P$.

*Proof.* Let $P_1 = \{(x_0, x_1), (x_1, x_2), \dots, (x_{n-1}, x_n)\}$, $P_2 = \{(y_0, y_1), (y_1, y_2), \dots, (y_{m-1}, y_m)\}$ be paths where $n \ge 2, m \ge 2$ and $(x_k, x_{k+1}) = (y_0, y_m)$ for some $k$. First notice that if $P_2$ satisfies only the first condition then

$$Q = P_1(x_0, x_k) \cup P_2 \cup P_1(x_{k+1}, x_n)$$

is a walk from which the required path can be obtained.

So suppose that $P_2$ satisfies the second condition. We shall complete the proof via induction on $|P_1|$. The second condition forces $|P_1| \ge 3$ and when $|P_1| = 3$, we either have $P_1 = \{(y_0, y_m), (x_1, x_2), (x_2, x_3)\}$ or $P_1 = \{(x_0, x_1), (x_1, x_2), (y_0, y_m)\}$ because $(y_0, y_m)$ can not be the middle edge of $P_1$ as otherwise the assumption $P_2 \cap P_1 \neq \emptyset$ force $P_2$ to visit $y_0$ or $y_m$ more than once, contradicting $P_2$ being a path. In the first case, since $x_1 = y_m$ we have $P_1 \cap P_2 = \{(x_2, x_3)\}$ and in the second case $x_2 = y_0$, so $P_1 \cap P_2 = \{(x_0, x_1)\}$. Notice that if $(x_2, x_3) \in P_2$ then $P_1(x_0, y_0) \cup P_2(y_0, x_3)$ is a walk for $(x_0, x_3)$ that does not visit $(y_0, y_m)$ and if $(x_0, x_1) \in P_2$ then $P_2(x_0, y_m) \cup P_1(y_m, x_3)$ is a walk for $(x_0, x_3)$ that does not visit $(y_0, y_m)$ so the base case is established.

Now let $P_1$ be a path of length $n$ where $n > 3$ and suppose that the statement holds for all paths of length $\le n - 1$. We either have $y_0 \neq x_0$ or $y_m \neq x_n$. If $y_0 \neq x_0$, that is, $(y_0, y_m) \in P_1 - \{(x_0, x_1)\}$ and if $(x_0, x_1) \in P_2$, $P_2(x_0, y_m) \cup P_1(y_m, x_n)$ is a path for $(x_0, x_n)$ that does not contain $(y_0, y_m)$, if $(x_0, x_1) \notin P_2$, it is guaranteed that $(P_1 \setminus \{(x_0, x_1)\}) \cap (P_2 \setminus \{(x_0, x_1)\}) \neq \emptyset$ and by induction hypothesis a path $P$ for $(x_1, x_n)$ not visiting $(y_0, y_m)$ exists. If $P$ visits $x_0$ then the required path is $P(x_0, x_n)$. If it does not visit $x_0$, then $\{(x_0, x_1)\} \cup P$ is the required path. Lastly, if $y_m \neq x_n$, then $(y_0, y_m) \in P_1 - \{(x_{n-1}, x_n)\}$ a case which we can resolve by a similar logic to the previous one. $\square$

Given a directed graph $D$ and factorizable edges $u, v \in D$, if for every $P \in \mathcal{P}(u)$ we have $v \in P$, we write $u \sim v$. An immediate consequence of the above lemma is the next theorem which establishes that the relation $\sim$ is symmetric.

**Theorem 2.2.** Let $D$ be a directed graph and $u, v \in D$. Then every path for $u$ contains $v$ if and only if every path for $v$ contains $u$.

*Proof.* Suppose that every path for $u$ contains $v$. Let $P$ be a path for $v$. Then $P$ satisfies none of the assumptions of Lemma 2.1 hence $u \in P$. $\square$
path for $(x, y)$ in $P$. Define the set $P(x, y)$ as follows:

$$P(x, y) = \begin{cases} Q & \text{if } (x, y) \notin P \\ (x, y) & \text{otherwise.} \end{cases}$$

**Lemma 2.1.** Let $D$ be a directed graph, $(x_0, x_n) \in D$ and $P_1$ be a path for $(x_0, x_n)$ in $D$. Let $(y_0, y_m) \in P_1$ and suppose that there exists a path $P_2$ for $(y_0, y_m)$ in $D$ satisfying any of the following conditions:

(i) $(x_0, x_n) \notin P_2$

(ii) $P_2 \cap P_1 \neq \emptyset$.

Then there exists a path $P$ for $(x_0, x_n)$ in $U$ such that $(y_0, y_m) \notin P$.

*Proof.* Let $P_1 = \{(x_0, x_1), (x_1, x_2), \dots, (x_{n-1}, x_n)\}$, $P_2 = \{(y_0, y_1), (y_1, y_2), \dots, (y_{m-1}, y_m)\}$ be paths where $n \ge 2, m \ge 2$ and $(x_k, x_{k+1}) = (y_0, y_m)$ for some $k$. First notice that if $P_2$ satisfies only the first condition then

$$Q = P_1(x_0, x_k) \cup P_2 \cup P_1(x_{k+1}, x_n)$$

is a walk from which the required path can be obtained.

So suppose that $P_2$ satisfies the second condition. We shall complete the proof via induction on $|P_1|$. The second condition forces $|P_1| \ge 3$ and when $|P_1| = 3$, we either have $P_1 = \{(y_0, y_m), (x_1, x_2), (x_2, x_3)\}$ or $P_1 = \{(x_0, x_1), (x_1, x_2), (y_0, y_m)\}$ because $(y_0, y_m)$ can not be the middle edge of $P_1$ as otherwise the assumption $P_2 \cap P_1 \neq \emptyset$ force $P_2$ to visit $y_0$ or $y_m$ more than once, contradicting $P_2$ being a path. In the first case, since $x_1 = y_m$ we have $P_1 \cap P_2 = \{(x_2, x_3)\}$ and in the second case $x_2 = y_0$, so $P_1 \cap P_2 = \{(x_0, x_1)\}$. Notice that if $(x_2, x_3) \in P_2$ then $P_1(x_0, y_0) \cup P_2(y_0, x_3)$ is a walk for $(x_0, x_3)$ that does not visit $(y_0, y_m)$ and if $(x_0, x_1) \in P_2$ then $P_2(x_0, y_m) \cup P_1(y_m, x_3)$ is a walk for $(x_0, x_3)$ that does not visit $(y_0, y_m)$ so the base case is established.

Now let $P_1$ be a path of length $n$ where $n > 3$ and suppose that the statement holds for all paths of length $\le n - 1$. We either have $y_0 \neq x_0$ or $y_m \neq x_n$. If $y_0 \neq x_0$, that is, $(y_0, y_m) \in P_1 - \{(x_0, x_1)\}$ and if $(x_0, x_1) \in P_2$, $P_2(x_0, y_m) \cup P_1(y_m, x_n)$ is a path for $(x_0, x_n)$ that does not contain $(y_0, y_m)$, if $(x_0, x_1) \notin P_2$, it is guaranteed that $(P_1 \setminus \{(x_0, x_1)\}) \cap (P_2 \setminus \{(x_0, x_1)\}) \neq \emptyset$ and by induction hypothesis a path $P$ for $(x_1, x_n)$ not visiting $(y_0, y_m)$ exists. If $P$ visits $x_0$ then the required path is $P(x_0, x_n)$. If it does not visit $x_0$, then $\{(x_0, x_1)\} \cup P$ is the required path. Lastly, if $y_m \neq x_n$, then $(y_0, y_m) \in P_1 - \{(x_{n-1}, x_n)\}$ a case which we can resolve by a similar logic to the previous one. $\square$

Given a directed graph $D$ and factorizable edges $u, v \in D$, if for every $P \in \mathcal{P}(u)$ we have $v \in P$, we write $u \sim v$. An immediate consequence of the above lemma is the next theorem which establishes that the relation $\sim$ is symmetric.

**Theorem 2.2.** Let $D$ be a directed graph and $u, v \in D$. Then every path for $u$ contains $v$ if and only if every path for $v$ contains $u$.

*Proof.* Suppose that every path for $u$ contains $v$. Let $P$ be a path for $v$. Then $P$ satisfies none of the assumptions of Lemma 2.1 hence $u \in P$. $\square$
Given a directed graph $D$ the factorizability dependency graph $\mathcal{FD}(D)$ of $D$ ($\mathcal{FD}$-graph in short) is defined as the graph of the relation $\sim$ on $D$.

Next we shall prove that not every undirected graph can be realized as an $\mathcal{FD}$-graph.

**Corollary 2.3.** Let $D$ be a directed graph. The graph $\mathcal{FD}(D)$ does not contain any cycle of length three, hence the relation $\sim$ is anti-transitive.

*Proof.* Suppose that $\sim$ is not antitransitive. Then there exists distinct edges $(a, b)$, $(c, d)$, $(e, f)$ of $D$ such that $(c, d) \sim (a, b) \sim (e, f)$ and $(c, d) \sim (e, f)$. Let $P_1$ be a path for $(c, d)$, $P_2$ be a path for $(a, b)$. Then from Theorem 2.2, $P_1$ visits $(a, b)$ and $(e, f)$, $P_2$ visits $(c, d)$ and $(e, f)$, but this yields a contradiction with Lemma 2.1 as $P_2 \cap P_1 \neq \emptyset$. $\square$

We end this section by providing a table of examples where several fundamental undirected graphs are realized as $\mathcal{FD}$-graphs. We should note that it is possible to realize polygons whose number of edges are higher than those presented, however we were unable to find a practical generalization for them. Also, the question of whether any triangle free graph can be realized as an $\mathcal{FD}$-graph is open.

<table><caption>**Table.** Examples of $\mathcal{FD}$-graphs.</caption><thead><tr><th>$D$</th><th>$\mathcal{FD}(D)$</th><th>Graph Symbol</th></tr></thead><tbody><tr><td><img src="image_1.png" alt="A directed graph with three nodes labeled e1, e2, e3, and edges e1-e2, e2-e3, and e1-e3"></td><td>$e_1 \sim e_2 \sim \dots \sim e_{2n-1} \sim e_{2n}$</td><td>$P_{2n}$</td></tr><tr><td><img src="image_2.png" alt="A directed graph with three nodes labeled e1, e2, e3, and edges e1-e2, e2-e3, and e1-e3"></td><td>$e_0 \sim e_1 \sim \dots \sim e_{2n-1} \sim e_{2n}$</td><td>$P_{2n-1}$</td></tr><tr><td><img src="image_3.png" alt="A directed graph with three nodes labeled e1, e2, e3, and edges e1-e2, e2-e3, and e1-e3"></td><td><img src="image_4.png" alt="A square graph with edge labels e1, e2, e3, and e4"></td><td>$C_4$</td></tr><tr><td><img src="image_5.png" alt="A directed graph with three nodes labeled e1, e2, e3, and edges e1-e2, e2-e3, and e1-e3"></td><td><img src="image_6.png" alt="A pentagon graph with edge labels e1, e2, e3, and e4"></td><td>$C_5$</td></tr><tr><td><img src="image_7.png" alt="A directed graph with three nodes labeled e1, e2, e3, and edges e1-e2, e2-e3, and e1-e3"></td><td><img src="image_8.png" alt="A graph with five nodes labeled e1, e2, e3, e4, and e5, and edges e1-e2, e2-e3, e3-e4, e4-e5, and e1-e5"></td><td>$K_{1,n}$</td></tr></tbody></table>
Given a directed graph $D$ the factorizability dependency graph $\mathcal{FD}(D)$ of $D$ ($\mathcal{FD}$-graph in short) is defined as the graph of the relation $\sim$ on $D$.

Next we shall prove that not every undirected graph can be realized as an $\mathcal{FD}$-graph.

**Corollary 2.3.** Let $D$ be a directed graph. The graph $\mathcal{FD}(D)$ does not contain any cycle of length three, hence the relation $\sim$ is anti-transitive.

*Proof.* Suppose that $\sim$ is not antitransitive. Then there exists distinct edges $(a, b)$, $(c, d)$, $(e, f)$ of $D$ such that $(c, d) \sim (a, b) \sim (e, f)$ and $(c, d) \sim (e, f)$. Let $P_1$ be a path for $(c, d)$, $P_2$ be a path for $(a, b)$. Then from Theorem 2.2, $P_1$ visits $(a, b)$ and $(e, f)$, $P_2$ visits $(c, d)$ and $(e, f)$, but this yields a contradiction with Lemma 2.1 as $P_2 \cap P_1 \neq \emptyset$. $\square$

We end this section by providing a table of examples where several fundamental undirected graphs are realized as $\mathcal{FD}$-graphs. We should note that it is possible to realize polygons whose number of edges are higher than those presented, however we were unable to find a practical generalization for them. Also, the question of whether any triangle free graph can be realized as an $\mathcal{FD}$-graph is open.

<table><caption>**Table.** Examples of $\mathcal{FD}$-graphs.</caption><thead><tr><th>$D$</th><th>$\mathcal{FD}(D)$</th><th>Graph Symbol</th></tr></thead><tbody><tr><td><img src="image_1.png" alt="A directed graph with three nodes labeled $e_1$, $e_2$, and $e_3$ and two edges: $e_1$ to $e_2$ and $e_2$ to $e_3$."></td><td>$e_1 \sim e_2 \sim \dots \sim e_{2n-1} \sim e_{2n}$</td><td>$P_{2n}$</td></tr><tr><td><img src="image_2.png" alt="A directed graph with three nodes labeled $e_1$, $e_2$, and $e_3$ and two edges: $e_1$ to $e_2$, $e_2$ to $e_3$, and $e_3$ to $e_1$."></td><td>$e_0 \sim e_1 \sim \dots \sim e_{2n-1} \sim e_{2n}$</td><td>$P_{2n-1}$</td></tr><tr><td><img src="image_3.png" alt="A directed graph with four nodes labeled $e_1$, $e_2$, $e_3$, and $e_4$ and two edges: $e_1$ to $e_2$, $e_2$ to $e_3$, and $e_3$ to $e_4$."></td><td><img src="image_4.png" alt="A square graph with side lengths $e_1$ and $e_2$."></td><td>$C_4$</td></tr><tr><td><img src="image_5.png" alt="A directed graph with five nodes labeled $e_1$, $e_2$, $e_3$, $e_4$, and $e_5$ and two edges: $e_1$ to $e_2$, $e_2$ to $e_3$, and $e_3$ to $e_4$."></td><td><img src="image_6.png" alt="A pentagon with side lengths $e_1$ and $e_2$."></td><td>$C_5$</td></tr><tr><td><img src="image_7.png" alt="A directed graph with six nodes labeled $e_1$, $e_2$, $e_3$, $e_4$, $e_5$, and $e_6$ and two edges: $e_1$ to $e_2$, $e_2$ to $e_3$, and $e_3$ to $e_4$."></td><td><img src="image_8.png" alt="A hexagon with side lengths $e_1$ and $e_2$."></td><td>$K_{1,n}$</td></tr></tbody></table>
### 3 Directed biclique coverings

Given a directed graph $D$, a set $\mathcal{C}$ of subgraphs of $D$ is called a *cover* of $D$ if every edge of $D$ is contained in at least one element of $\mathcal{C}$. The *minimum directed biclique covering size* $m(D)$ of $D$ is the minimum number of directed biclique subgraphs required to cover $D$.

We shall briefly discuss how an analogue of the above notion appears in the representation theory of finite sets. Given a finite set $X$, a correspondence is a subset $U \subseteq X \times X$. A block of $U$ is a subset of the form $A \times B$ where $A \times B \subseteq U$. A block decomposition of $U$ is a collection $\{A_i \times B_i\}_i$ of blocks where $U = \cup_i A_i \times B_i$. Notice that blocks of $U$ are exactly its directed bicliques when one considers $U$ as a directed graph. An important invariant of $U$ is the minimum number of blocks it can be written as union of, which is $m(U)$. This invariant was used in [3] as a way to decide whether a correspondence is essential or not, that is, whether it can be written as a particular product of correspondences which are "smaller". The usefulness of this notion is that a classical approach in functorial representation theory involves utilizing the simple modules of the algebra of essential elements to understand the simple functors.

The next proposition will reveal a surprising connection between particular structural invariants of $D$ and $\mathcal{FD}$. We note that it does not generalize to chains whose length is longer than 2.

**Proposition 3.1.** Let $D$ be a directed graph, $a, b, c \in \mathcal{FD}(D)$. Suppose one of the following holds:

(i) $a \sim b$

(ii) $a \sim c \sim b$.

Then $a$ and $b$ can't be in the same directed biclique of $D$.

*Proof.* Suppose that $a$ and $b$ lie in the same directed biclique so that $\{(a_i, b_t), (b_i, a_t)\} \subseteq D$. First assume that $a \sim b$. Let $P \in \mathcal{P}(a)$. If $b_t \neq a_t$, then $(a_i, b_t) \cup P(b_t, a_t)$ constitutes as a path for $a$ that does not visit $b$ and if $a_i \neq b_i$ then $P(a_i, b_i) \cup (b_i, a_t)$ is a path that contradicts $a \sim b$. Now assume that $a \sim c \sim b$. Notice that this assumption forces $a_i \neq b_i$ and $a_t \neq b_t$ as otherwise one can find a path for $c$ that does not visit $a$ or $b$ because they share a vertex. Without loss of generality let $Q$ be a path for $c$ which visits $a$ before $b$. Then $Q(c_i, a_i) \cup (a_i, b_t) \cup Q(b_t, c_t)$ is a path for $c$ that does not visit $b$. $\square$

Let $G$ be an undirected graph. The chromatic number $\chi(p, G)$ of $G$ relative to $p$ is defined as the minimum number of colors required for colouring the vertices of $G$ such that vertices which are of distance not greater than $p$ from each other have distinct colors. So one has $\chi(G) = \chi(1, G)$ where $\chi$ denotes the ordinary chromatic number. The $p$th power $G^p$ of $G$ is defined to be the graph which has the same vertex set as $G$ and has an edge between any pair of vertices which are at a distance not greater than $p$ from each other. To define the chromatic number relative to $p$, one can also use the identification $\gamma(p, G) = \chi(G^p)$.

By considering the coloring of $\mathcal{FD}(D)$ by directed bicliques, one gets the following surprising connection.

**Corollary 3.2.** Let $D$ be a directed graph. Then $m(D) \ge \chi(2, \mathcal{FD}(D))$.
### 3 Directed biclique coverings

Given a directed graph $D$, a set $\mathcal{C}$ of subgraphs of $D$ is called a *cover* of $D$ if every edge of $D$ is contained in at least one element of $\mathcal{C}$. The *minimum directed biclique covering size* $m(D)$ of $D$ is the minimum number of directed biclique subgraphs required to cover $D$.

We shall briefly discuss how an analogue of the above notion appears in the representation theory of finite sets. Given a finite set $X$, a correspondence is a subset $U \subseteq X \times X$. A block of $U$ is a subset of the form $A \times B$ where $A \times B \subseteq U$. A block decomposition of $U$ is a collection $\{A_i \times B_i\}_i$ of blocks where $U = \cup_i A_i \times B_i$. Notice that blocks of $U$ are exactly its directed bicliques when one considers $U$ as a directed graph. An important invariant of $U$ is the minimum number of blocks it can be written as union of, which is $m(U)$. This invariant was used in [3] as a way to decide whether a correspondence is essential or not, that is, whether it can be written as a particular product of correspondences which are "smaller". The usefulness of this notion is that a classical approach in functorial representation theory involves utilizing the simple modules of the algebra of essential elements to understand the simple functors.

The next proposition will reveal a surprising connection between particular structural invariants of $D$ and $\mathcal{FD}$. We note that it does not generalize to chains whose length is longer than 2.

**Proposition 3.1.** Let $D$ be a directed graph, $a, b, c \in \mathcal{FD}(D)$. Suppose one of the following holds:

(i) $a \sim b$

(ii) $a \sim c \sim b$.

Then $a$ and $b$ can't be in the same directed biclique of $D$.

*Proof.* Suppose that $a$ and $b$ lie in the same directed biclique so that $\{(a_i, b_t), (b_i, a_t)\} \subseteq D$. First assume that $a \sim b$. Let $P \in \mathcal{P}(a)$. If $b_t \neq a_t$, then $(a_i, b_t) \cup P(b_t, a_t)$ constitutes as a path for $a$ that does not visit $b$ and if $a_i \neq b_i$ then $P(a_i, b_i) \cup (b_i, a_t)$ is a path that contradicts $a \sim b$. Now assume that $a \sim c \sim b$. Notice that this assumption forces $a_i \neq b_i$ and $a_t \neq b_t$ as otherwise one can find a path for $c$ that does not visit $a$ or $b$ because they share a vertex. Without loss of generality let $Q$ be a path for $c$ which visits $a$ before $b$. Then $Q(c_i, a_i) \cup (a_i, b_t) \cup Q(b_t, c_t)$ is a path for $c$ that does not visit $b$. $\square$

Let $G$ be an undirected graph. The chromatic number $\chi(p, G)$ of $G$ relative to $p$ is defined as the minimum number of colors required for colouring the vertices of $G$ such that vertices which are of distance not greater than $p$ from each other have distinct colors. So one has $\chi(G) = \chi(1, G)$ where $\chi$ denotes the ordinary chromatic number. The $p$th power $G^p$ of $G$ is defined to be the graph which has the same vertex set as $G$ and has an edge between any pair of vertices which are at a distance not greater than $p$ from each other. To define the chromatic number relative to $p$, one can also use the identification $\gamma(p, G) = \chi(G^p)$.

By considering the coloring of $\mathcal{FD}(D)$ by directed bicliques, one gets the following surprising connection.

**Corollary 3.2.** Let $D$ be a directed graph. Then $m(D) \ge \chi(2, \mathcal{FD}(D))$.
# 4 The graph WFD(D)

We now present another way of constructing undirected graphs from directed graphs which encodes much more information regarding the control of edges on reachability properties of subgraphs. Let $D$ be a directed graph and $D' \subseteq D$ a subgraph. We write $D' < D$ if $D'$ is an equivalent subgraph of $D$. An edge of $D$ is called redundant if it is not contained in any of the minimal equivalent subgraphs of $D$. The set of all redundant edges of $D$ will be denoted by $\mathcal{R}(D)$ whereas we use $\mathcal{F}(D)$ to denote the set of all factorizable edges of $D$. Given two edges $u, v \in \mathcal{F}(D)$, we write $u \approx v$ if there exists a subgraph $D' < D$ such that $u \sim v$ in $D'$. We define the weak factorizability dependency graph of $D$ (WFD-graph in short) as the graph of the relation $\approx$ on $D$.

The proof of the next statement is trivial.

**Proposition 4.1.** Let $D$ be a directed graph. Then $V(\mathcal{WFD}(D)) = \mathcal{F}(D) \cup \mathcal{R}(D)$.

The next theorem provides critical insight into the structure of $\mathcal{WFD}(D)$.

**Theorem 4.2.** Let $D$ be a directed graph, $a, b \in D$ such that $a \approx b, a \not\approx b$. Also let $S \subseteq D$ be a minimal subgraph for which $(D \setminus S) < D$ and $a \sim b$ in $D \setminus S$. Then for any $x \in S$, we have $a \sim x$ in $D \setminus S'$ where $S' = (S \cup \{b\}) \setminus \{x\}$.

*Proof.* Let $D' = (D \setminus S) \cup \{x\} = (D \setminus S') \cup \{b\}$. The minimality of $S$ implies that $a \not\approx b$ in $D'$. Moreover $b \in \mathcal{F}(D \setminus S)$ so in $D'$ we have $b \not\approx x$, hence $\{a, x\} \subseteq \mathcal{F}(D' \setminus \{b\})$.

We claim that for every $Q \in \mathcal{P}_{D'}(x)$, we have $Q \cap \{a, b\} \not\subseteq \emptyset$. Assume the contrary and let $Q \in \mathcal{P}_{D'}(x)$ be a path where $Q \cap \{a, b\} = \emptyset$. Take $P \in \mathcal{P}_{D'}(a)$ such that $b \notin P \ni x$. Such $P$ exists since $a \not\approx b \in D'$ but $a \sim b$ in $D' \setminus \{x\}$. Now we can construct the walk $P(a_i, x_i) \cup Q \cup P(x_t, a_t)$ for $a$ in $G \setminus S$ which does not visit $b$, contradiction with $a \sim b$ in $G \setminus S$. So the claim holds. Hence, every path for $x$ in $D'$ contains $a$ or $b$, so removing $b$ yields $a \sim x$ in $D \setminus S'$. $\square$

Given a directed graph $D$, a *dependency clique* of $D$ is a minimal (with respect to containment) subset $S \subseteq D$ such that for a pair of edges $a, b \in S$ with $a \approx b$, we have $a \sim b$ in $(D \setminus S) \cup \{a, b\}$.

Theorem 4.2 allows us to write $x$ in the place of $a$ or $b$. A direct consequence is the following justification of our choice for the name of the subset $S$.

**Corollary 4.3.** *Assuming the notation from Theorem 4.2 for any distinct pair $x, y \in S$, one has $a \approx x, b \approx x$ and $x \approx y$. Thus, a dependency clique forms a clique subgraph of $\mathcal{WFD}(D)$.*

Next we will explore the conditions for a given set $S$ to be a dependency clique.

**Theorem 4.4.** Let $S \subseteq D$ be a directed graph, $S \subseteq D$. Then $S$ is a dependency clique of $D$ if and only if it satisfies the following conditions:

(i) $|S| > 1$

(ii) For every distinct pair $a, b \in S$, there exists a path $P \in \mathcal{P}(a)$ such that $P \cap S = \{b\}$

(iii) For every $P \in \mathcal{P}(S)$, one has $P \cap S \not\ni \emptyset$.
# 4 The graph WFD(D)

We now present another way of constructing undirected graphs from directed graphs which encodes much more information regarding the control of edges on reachability properties of subgraphs. Let $D$ be a directed graph and $D' \subseteq D$ a subgraph. We write $D' < D$ if $D'$ is an equivalent subgraph of $D$. An edge of $D$ is called redundant if it is not contained in any of the minimal equivalent subgraphs of $D$. The set of all redundant edges of $D$ will be denoted by $\mathcal{R}(D)$ whereas we use $\mathcal{F}(D)$ to denote the set of all factorizable edges of $D$. Given two edges $u, v \in \mathcal{F}(D)$, we write $u \approx v$ if there exists a subgraph $D' < D$ such that $u \sim v$ in $D'$. We define the weak factorizability dependency graph of $D$ (WFD-graph in short) as the graph of the relation $\approx$ on $D$.

The proof of the next statement is trivial.

**Proposition 4.1.** Let $D$ be a directed graph. Then $V(\mathcal{WFD}(D)) = \mathcal{F}(D) \cup \mathcal{R}(D)$.

The next theorem provides critical insight into the structure of $\mathcal{WFD}(D)$.

**Theorem 4.2.** Let $D$ be a directed graph, $a, b \in D$ such that $a \approx b, a \not\approx b$. Also let $S \subseteq D$ be a minimal subgraph for which $(D \setminus S) < D$ and $a \sim b$ in $D \setminus S$. Then for any $x \in S$, we have $a \sim x$ in $D \setminus S'$ where $S' = (S \cup \{b\}) \setminus \{x\}$.

*Proof.* Let $D' = (D \setminus S) \cup \{x\} = (D \setminus S') \cup \{b\}$. The minimality of $S$ implies that $a \not\approx b$ in $D'$. Moreover $b \in \mathcal{F}(D \setminus S)$ so in $D'$ we have $b \not\approx x$, hence $\{a, x\} \subseteq \mathcal{F}(D' \setminus \{b\})$.

We claim that for every $Q \in \mathcal{P}_{D'}(x)$, we have $Q \cap \{a, b\} \not\subseteq \emptyset$. Assume the contrary and let $Q \in \mathcal{P}_{D'}(x)$ be a path where $Q \cap \{a, b\} = \emptyset$. Take $P \in \mathcal{P}_{D'}(a)$ such that $b \notin P \ni x$. Such $P$ exists since $a \not\approx b \in D'$ but $a \sim b$ in $D' \setminus \{x\}$. Now we can construct the walk $P(a_i, x_i) \cup Q \cup P(x_t, a_t)$ for $a$ in $G \setminus S$ which does not visit $b$, contradiction with $a \sim b$ in $G \setminus S$. So the claim holds. Hence, every path for $x$ in $D'$ contains $a$ or $b$, so removing $b$ yields $a \sim x$ in $D \setminus S'$. $\square$

Given a directed graph $D$, a *dependency clique* of $D$ is a minimal (with respect to containment) subset $S \subseteq D$ such that for a pair of edges $a, b \in S$ with $a \approx b$, we have $a \sim b$ in $(D \setminus S) \cup \{a, b\}$.

Theorem 4.2 allows us to write $x$ in the place of $a$ or $b$. A direct consequence is the following justification of our choice for the name of the subset $S$.

**Corollary 4.3.** *Assuming the notation from Theorem 4.2 for any distinct pair $x, y \in S$, one has $a \approx x, b \approx x$ and $x \approx y$. Thus, a dependency clique forms a clique subgraph of $\mathcal{WFD}(D)$.*

Next we will explore the conditions for a given set $S$ to be a dependency clique.

**Theorem 4.4.** Let $S \subseteq D$ be a directed graph, $S \subseteq D$. Then $S$ is a dependency clique of $D$ if and only if it satisfies the following conditions:

(i) $|S| > 1$

(ii) For every distinct pair $a, b \in S$, there exists a path $P \in \mathcal{P}(a)$ such that $P \cap S = \{b\}$

(iii) For every $P \in \mathcal{P}(S)$, one has $P \cap S \not\ni \emptyset$.
*Proof.* First suppose that $S$ is a dependency clique. The first and the third conditions holds trivially. Let $\{a, b\} \subseteq S$. The second condition follows from the fact that $a \sim b$ in $(D \setminus S) \cup \{a, b\}$ but $a \not\sim b$ in any larger equivalent subgraph.

Now suppose that $S$ satisfies the three assumptions. First condition allows us to let $\{a, b\} \subseteq S$. Let $S' = S \setminus \{a, b\}, D' = D \setminus S'$. We claim that $a \sim b$ in $D'$. By the second condition, it is clear that $a, b \in \mathcal{F}(D')$. The third and second conditions imply the minimality of $S$ and that for every $P \in \mathcal{P}_{D'}(b)$, we have $a \in P$. Hence $a \sim b$ in $D'$.

□

Given a path $P$ in a directed graph $D$, we let $o_P(a)$ denote the order in which the edge $e$ is visited by the path $P$.

**Corollary 4.5.** Let $D$ be a directed graph, $S \subseteq D$ a dependency clique. Then for every $t \in D \setminus S$, there exists an $s \in S$ such that $t \not\sim s$.

*Proof.* Assume the contrary, let $S$ be a dependency clique, $t \in D$ an edge such that $t \sim s$ for every $s \in S$. Let $P \in \mathcal{P}(t)$ and $s \in S$ be such that $o_P(s) > o_P(s')$ for every $s' \in S \setminus \{s\}$. Also let $Q \in \mathcal{P}(s)$ be a path where $Q \cap S = \{r\}$. If $o_Q(r) > o_Q(t)$, then $Q(s_i, t_i) \cup P(t_i, r_i) \cup Q(r_i, s_t)$ is a walk for $s$ that does not visit $t$, contradicting $t \sim s$.

Now suppose $o_Q(r) < o_Q(t)$, let $R \in \mathcal{P}(r)$ be a path where $R \cap S = \{s\}$. Now if $o_R(s) < o_R(t)$, then $P(t_i, r_i) \cup R(r_i, s_i) \cup P(s_i, t_i)$ is a walk for $t$ that does not visit $r$, contradicting $t \sim r$.

Lastly, if $o_R(s) > o_R(t)$ then $Q(s_i, r_i) \cup R(r_i, t_i) \cup Q(t_i, s_t)$ is a path for $s$ that does not visit any element of $S$, contradicting the third condition of Theorem 4.4. □

# 5 The Lattice of Equivalent Subgraphs of $D$

Let $G$ be an undirected graph. An *independent set* of $G$ is a subset $I \subseteq V(G)$ such that no two vertices in $I$ are adjacent whereas a *dominating set* of $G$ is a subset $S \subseteq V(G)$ such that every $v \in V(G) \setminus S$ is adjacent to a vertex in $S$. A set is *independent dominating* if it is both independent and dominating.

Let $E$ be a finite poset. Given subsets $S, T \subseteq E$, their *join* (least upper bound) is denoted by $S \vee T$, whereas $S \wedge T$ denotes their *meet* (greatest lower bound). We say $E$ is a *join* (resp. *meet*) *semilattice* if it is closed under $\vee$ (resp. $\wedge$) and denote its largest (resp. smallest) element with $1_E$ (resp $0_E$). The poset $E$ is a *lattice* if it is both join and meet semilattice.

Assuming the partial orders to be inclusion, the poset of independent sets of $G$ forms a meet-semilattice and for a directed graph $D$ the poset of equivalent subgraphs of $D$ forms a join-semilattice. Both of these posets can be extended to a lattice by letting the greatest (resp. least) element to be $G$ (resp. $\emptyset$). We denote these lattices by $\mathcal{I}_G$ and $\mathcal{S}_D$, respectively.

A *lattice homomorphism* between two lattices is a function that preserves meet and join operations. A *lattice isomorphism* is a bijective lattice homomorphism. For a poset $\mathcal{P}$ let $\mathcal{P}^{\text{op}}$ denote its opposite poset. The following results follows from the observation that removal of any independent set of $\mathcal{FD}(D)$ from $D$ yields an equivalent subgraph.

**Proposition 5.1.** Let $D$ be a directed graph. Then the map between the independent sets of $\mathcal{FD}(D)$ and the equivalent subgraphs of $D$ given by $I \leftrightarrow D \setminus I$ is a bijection which sends the independent dominating sets of $\mathcal{FD}(D)$ to the minimal equivalent subgraphs of $D$. Moreover, it yields an isomorphism

$$ \mathcal{I}_{\mathcal{FD}(D)} \cong (\mathcal{S}_D)^{\text{op}}. $$
**Proof.** First suppose that $S$ is a dependency clique. The first and the third conditions holds trivially. Let $\{a, b\} \subseteq S$. The second condition follows from the fact that $a \sim b$ in $(D \setminus S) \cup \{a, b\}$ but $a \nmid b$ in any larger equivalent subgraph.

Now suppose that $S$ satisfies the three assumptions. First condition allows us to let $\{a, b\} \subseteq S$. Let $S' = S \setminus \{a, b\}, D' = D \setminus S'$. We claim that $a \sim b$ in $D'$. By the second condition, it is clear that $a, b \in \mathcal{F}(D')$. The third and second conditions imply the minimality of $S$ and that for every $P \in \mathcal{P}_{D'}(b)$, we have $a \in P$. Hence $a \sim b$ in $D'$.

□

Given a path $P$ in a directed graph $D$, we let $o_P(a)$ denote the order in which the edge $e$ is visited by the path $P$.

**Corollary 4.5.** Let $D$ be a directed graph, $S \subseteq D$ a dependency clique. Then for every $t \in D \setminus S$, there exists an $s \in S$ such that $t \nmid s$.

**Proof.** Assume the contrary, let $S$ be a dependency clique, $t \in D$ an edge such that $t \sim s$ for every $s \in S$. Let $P \in \mathcal{P}(t)$ and $s \in S$ be such that $o_P(s) > o_P(s')$ for every $s' \in S \setminus \{s\}$. Also let $Q \in \mathcal{P}(s)$ be a path where $Q \cap S = \{r\}$. If $o_Q(r) > o_Q(t)$, then $Q(s_i, t_i) \cup P(t_i, r_i) \cup Q(r_i, s_t)$ is a walk for $s$ that does not visit $t$, contradicting $t \sim s$.

Now suppose $o_Q(r) < o_Q(t)$, let $R \in \mathcal{P}(r)$ be a path where $R \cap S = \{s\}$. Now if $o_R(s) < o_R(t)$, then $P(t_i, r_i) \cup R(r_i, s_i) \cup P(s_i, t_i)$ is a walk for $t$ that does not visit $r$, contradicting $t \sim r$.

Lastly, if $o_R(s) > o_R(t)$ then $Q(s_i, r_i) \cup R(r_i, t_i) \cup Q(t_i, s_t)$ is a path for $s$ that does not visit any element of $S$, contradicting the third condition of Theorem 4.4. □

# 5 The Lattice of Equivalent Subgraphs of $D$

Let $G$ be an undirected graph. An *independent set* of $G$ is a subset $I \subseteq V(G)$ such that no two vertices in $I$ are adjacent whereas a *dominating set* of $G$ is a subset $S \subseteq V(G)$ such that every $v \in V(G) \setminus S$ is adjacent to a vertex in $S$. A set is *independent dominating* if it is both independent and dominating.

Let $E$ be a finite poset. Given subsets $S, T \subseteq E$, their *join* (least upper bound) is denoted by $S \vee T$, whereas $S \wedge T$ denotes their *meet* (greatest lower bound). We say $E$ is a *join* (resp. *meet*) *semilattice* if it is closed under $\vee$ (resp. $\wedge$) and denote its largest (resp. smallest) element with $1_E$ (resp $0_E$). The poset $E$ is a *lattice* if it is both join and meet semilattice.

Assuming the partial orders to be inclusion, the poset of independent sets of $G$ forms a meet-semilattice and for a directed graph $D$ the poset of equivalent subgraphs of $D$ forms a join-semilattice. Both of these posets can be extended to a lattice by letting the greatest (resp. least) element to be $G$ (resp. $\emptyset$). We denote these lattices by $\mathcal{I}_G$ and $\mathcal{S}_D$, respectively.

A *lattice homomorphism* between two lattices is a function that preserves meet and join operations. A *lattice isomorphism* is a bijective lattice homomorphism. For a poset $\mathcal{P}$ let $\mathcal{P}^{\text{op}}$ denote its opposite poset. The following results follows from the observation that removal of any independent set of $\mathcal{FD}(D)$ from $D$ yields an equivalent subgraph.

**Proposition 5.1.** Let $D$ be a directed graph. Then the map between the independent sets of $\mathcal{FD}(D)$ and the equivalent subgraphs of $D$ given by $I \leftrightarrow D \setminus I$ is a bijection which sends the independent dominating sets of $\mathcal{FD}(D)$ to the minimal equivalent subgraphs of $D$. Moreover, it yields an isomorphism

$$ \mathcal{I}_{\mathcal{FD}(D)} \cong (\mathcal{S}_D)^{\text{op}}. $$
Now let us investigate the lattice $S_D$. An element $e \in E$ is called an *atom* if it is minimal among the non-zero elements. Note that minimal equivalent subgraphs are atoms of $S_D$. Let $\mathcal{L}$ be a lattice. A *sublattice* $S$ of $\mathcal{L}$ is a nonempty subset of $\mathcal{L}$ that is closed under the meet and the join operations of $\mathcal{L}$. A *chain* $C$ in $\mathcal{L}$ is a subset of $\mathcal{L}$ such that for every $x, y \in C$, either $x \le y$ or $y \le x$ whereas the *height* of $\mathcal{L}$ is the maximum cardinality of a chain in $\mathcal{L}$. We denote the finite lattice of height 3 having exactly $n$ atoms with $M_n$.

<figure><img src="image_2.png" /><figcaption>**Figure.** The lattice $M_n$.</figcaption></figure>

We call a directed graph $D$ *predictable* if $\mathcal{FD}(D) \cong \mathcal{WFD}(D)$. Although this is a strong restriction, we will see that it reveals interesting features, as opposed to trivializing the structure.

**Lemma 5.2.** Let $D$ be a predictable directed graph. Let $U$ and $V$ be two minimal equivalent subgraphs of $D$ and $N = U \cup V$. Then for every $u \in (N \setminus U)$, there exists a $v \in N \setminus V$ such that $u \sim v$.

*Proof.* Suppose not, let $u \in N \setminus U$ where for every $v \in N \setminus V$ we have $u \not\sim v$. Notice that the sets $N \setminus U$ and $N \setminus V$ are disjoint so $u \in V$. Now since $D$ is predictable, $u$ is still factorizable in $V$ which contradicts $V$ being a minimal equivalent subgraph. $\square$

**Theorem 5.3.** If $M_3$ is a sublattice of $S_D$ where the atoms are minimal equivalent subgraphs, then $\mathcal{FD}(D)$ contains a cycle of length $\ge 6$.

*Proof.* The assumption implies that there exists distinct minimal equivalent subgraphs $G_1, G_2$ and $G_3$ such that for $1 \le i < j \le 3$ we have $G_i \vee G_j = 1_{M_3} = G_1 \vee G_2 \vee G_3$. Now let $e_1 \sim e_2 \sim e_3 \sim \dots \sim e_k$ be a chain of maximal length subject to the condition that given $l \equiv i \mod 3$, we have $e_l \in G_i$. Lemma 5.2, together with the fact that for $i \ge 3$ we have $e_i \not\sim e_{i-2}$ (otherwise we get a triangle) implies that $k \ge 6$. By maximality, $e_k \sim e_i$ for some $i \le k$ where $i \equiv k+1 \mod 3$. It is clear that $i \not\equiv k-2$, hence $e_i \sim e_{i+1} \sim \dots \sim e_k \sim e_i$ is a cycle of length $\ge 6$. $\square$

## References

[1] Abboud, A., Bodwin, G., Reachability Preservers: New Extremal Bounds and Approximation Algorithms., *SIAM Journal on Computing* **53**(2), 221-246 (2024).

[2] Aho, A. V., Garey, M.R., Ullman, J.D., The transitive reduction of a directed graph, *SIAM Journal on Computing* **2**, 131-137 (1972).

[3] Bouc, S., Thévenaz, J., The algebra of essential relations on a finite set, *Journal für die Reine und Angewandte Mathematik.*, **712**, 225-250 (2016).

[4] Fleischner H., Mujuni E., Paulusma D., Szeider S., Covering graphs with few complete bipartite subgraphs, *Theoretical Computer Science* **410**, 2045-2053 (2009).
Now let us investigate the lattice $S_D$. An element $e \in E$ is called an *atom* if it is minimal among the non-zero elements. Note that minimal equivalent subgraphs are atoms of $S_D$. Let $\mathcal{L}$ be a lattice. A *sublattice* $S$ of $\mathcal{L}$ is a nonempty subset of $\mathcal{L}$ that is closed under the meet and the join operations of $\mathcal{L}$. A *chain* $C$ in $\mathcal{L}$ is a subset of $\mathcal{L}$ such that for every $x, y \in C$, either $x \le y$ or $y \le x$ whereas the *height* of $\mathcal{L}$ is the maximum cardinality of a chain in $\mathcal{L}$. We denote the finite lattice of height 3 having exactly $n$ atoms with $M_n$.

<figure><img src="image_3.png" /><figcaption>**Figure.** The lattice $M_n$.</figcaption></figure>

We call a directed graph $D$ *predictable* if $\mathcal{FD}(D) \cong \mathcal{WFD}(D)$. Although this is a strong restriction, we will see that it reveals interesting features, as opposed to trivializing the structure.

**Lemma 5.2.** Let $D$ be a predictable directed graph. Let $U$ and $V$ be two minimal equivalent subgraphs of $D$ and $N = U \cup V$. Then for every $u \in (N \setminus U)$, there exists a $v \in N \setminus V$ such that $u \sim v$.

*Proof.* Suppose not, let $u \in N \setminus U$ where for every $v \in N \setminus V$ we have $u \not\sim v$. Notice that the sets $N \setminus U$ and $N \setminus V$ are disjoint so $u \in V$. Now since $D$ is predictable, $u$ is still factorizable in $V$ which contradicts $V$ being a minimal equivalent subgraph. $\square$

**Theorem 5.3.** If $M_3$ is a sublattice of $S_D$ where the atoms are minimal equivalent subgraphs, then $\mathcal{FD}(D)$ contains a cycle of length $\ge 6$.

*Proof.* The assumption implies that there exists distinct minimal equivalent subgraphs $G_1, G_2$ and $G_3$ such that for $1 \le i < j \le 3$ we have $G_i \vee G_j = 1_{M_3} = G_1 \vee G_2 \vee G_3$. Now let $e_1 \sim e_2 \sim e_3 \sim \dots \sim e_k$ be a chain of maximal length subject to the condition that given $l \equiv i \mod 3$, we have $e_l \in G_i$. Lemma 5.2, together with the fact that for $i \ge 3$ we have $e_i \not\sim e_{i-2}$ (otherwise we get a triangle) implies that $k \ge 6$. By maximality, $e_k \sim e_i$ for some $i \le k$ where $i \equiv k+1 \mod 3$. It is clear that $i \not\equiv k-2$, hence $e_i \sim e_{i+1} \sim \dots \sim e_k \sim e_i$ is a cycle of length $\ge 6$. $\square$

## References

[1] Abboud, A., Bodwin, G., Reachability Preservers: New Extremal Bounds and Approximation Algorithms., *SIAM Journal on Computing* **53**(2), 221-246 (2024).

[2] Aho, A. V., Garey, M.R., Ullman, J.D., The transitive reduction of a directed graph, *SIAM Journal on Computing* **2**, 131-137 (1972).

[3] Bouc, S., Thévenaz, J., The algebra of essential relations on a finite set, *Journal für die Reine und Angewandte Mathematik.*, **712**, 225-250 (2016).

[4] Fleischner H., Mujuni E., Paulusma D., Szeider S., Covering graphs with few complete bipartite subgraphs, *Theoretical Computer Science* **410**, 2045-2053 (2009).
[5] Hefner, K. A. S., Directed Biclique Covers and Partitions of Digraphs, PhD Diss., University of Colorado (1988). https://digital.auraria.edu/work/ns/76c803dd-7d16-4dd9-9d0ed163d4aa0bcb

[6] Moyles, D. M., Thompson, G.L., An Algorithm for Finding a Minimum Equivalent Graph of a Digraph, *Journal of the ACM* **16**, 455-460 (1969).
[5] Hefner, K. A. S., Directed Biclique Covers and Partitions of Digraphs, PhD Diss., University of Colorado (1988). https://digital.auraria.edu/work/ns/76c803dd-7d16-4dd9-9d0ed163d4aa0bcb

[6] Moyles, D. M., Thompson, G.L., An Algorithm for Finding a Minimum Equivalent Graph of a Digraph, *Journal of the ACM* **16**, 455-460 (1969).