A DIGRAH ON RESIDUATED LATTICES

FOTSO LEKOBOU RODRIGUES SOCRATES¹ ATAMEWOUE TSAFACK SURDIVE² KIANPI MAURICE¹ DIÉKOUAM FOTSO LUC ÉMÉRY³

¹ Department of Mathematics, University of Yaoundé 1, Cameroon

² Higher Teachers' Training College, University of Yaoundé 1, Cameroon

³ Higher Teachers' Training College, University of Maroua, Cameroon

received, revised, accepted.

We introduce a digraph (directed graph) on bounded residuated lattice. We prove that the undirected graph associated to the digraph is connected and its diameter is at most 2. In addition, using the properties of the digraph, it is given some conditions under which a bounded residuated lattice is: *MV-algebra; MTL-algebra*. We prove that every dominating set of a strongly connected digraph constructed on a residuated lattice is an *MTL-filters*. We also prove that residuated lattices homomorphisms are digraphs homomorphisms.

**Keywords:** graph; residuated lattice; *MTL*-algebra; *MV*-algebra; *MTL*-filter.

# 1 Introduction

The data representation has all the time been an important matter in the field of Mathematics. Graph theory therefore appears as a solution to this problem. Graphs are mathematical structures used to model pairwise relations between objects. Graph theory has found its applications in engineering and computer science [Banasode and Umathar(2018), Singh(2014), Vinutha and Arathi(2015)], also in many daily life problems like wedding problem; time table problem [Bondy et al.(1976)Bondy, Murty, et al.].

The connection between graph theory and algebra structure, with the hope that this will be mutually beneficial for both of them came from the Beck's work [Beck(1988)]. He introduced the notion of zero-divisor graph on commutative rings and used it to define coloring ring. On a commutative ring $R$, Anderson and Livingston [Anderson and Badawi(2008)] investigated the link between the ring-theoretic properties of $R$ and the graph-theoretic properties of a simple graph $\Gamma(R)$. Following the same trend, Lida et al. [Torkzadeh and Ahmadpanah(2014)] study the zero-divisor graph in residuated lattice. Gan et al. [Gan and Yang(2020)] introduced and study the zero-divisor graphs on MV-algebras and they succeeded to classify all MV-algebras of cardinality up to seven. In [Kologani et al.(2019)Kologani, Borzooei, and Kim] the authors constructed implicative graph on a Hoop algebra, showed that it is connected and gave conditions
under which it is a star or a tree.

Most often, the connection between graphs and algebras structures consists in constructing graph from properties of algebra but it does not unveil the importance of these graphs for the algebraic structure. In this work we establish the connection between graph theory and residuated lattices. More precisely, we use the properties of the digraph derived from a residuated lattice to characterize it. To achieve that goal, the paper is organized as follows. In Section 2, we review some basic definitions and results about residuated lattices and graph theory. In Section 3, given a residuated lattice $\mathbf{L}$, we introduce a digraph $D(L)$. These digraphs are weakly connected and the associated undirected graph is connected with diameter at most 2. We prove that the implicative graph introduced by Kologani in [Kologani et al. (2019) Kologani, Borzooei, and Kim] is a subgraph of the undirected graph associated to a digraph $D(L)$; both of them constructed on the same residuated lattice. In Section 4 some properties of residuated lattices are studied based on the digraphs $D(L)$. In fact exploiting the properties of the digraph constructed from a residuated lattice, we give conditions under which the residuated lattice is either an *MV*-algebra or an *MTL*-algebra. We prove that every dominating set of a strongly connected digraph $D(L)$ of a bounded residuated lattice $\mathbf{L}$ is an *MTL*-filters. We also prove in section 5 that residuated lattices homomorphisms are digraphs homomorphisms.

## 2 Fundamentals on residuated lattices and graphs theory

In this section, we recall the definition of a bounded residuated lattice, Hoop algebra and give some useful related properties. For the better understanding of the work, we recall also some basics notions from graph theory.

**Definition 2.1.** [Galatos et al. (2007) Galatos, Jipsen, Kowalski, and Ono] A bounded commutative residuated lattice is an algebraic structure $\mathbf{L} = (L; \wedge, \vee, \odot, \rightarrow, 0, 1)$ defined on a non empty set $L$ where:

1. $(L; \wedge, \vee, 0, 1)$ is a bounded lattice;

2. $(L; \odot, 1)$ is a commutative monoid with unit element 1;

3. for all $x, y, z \in L, z \le x \rightarrow y$ if and only if $x \odot z \le y$.

From now on, all the residuated lattices will be considered to be commutative.

The following proposition provides some properties of bounded residuated lattices. These properties are very useful for calculus on residuated lattices

**Proposition 2.1.** [Galatos et al. (2007) Galatos, Jipsen, Kowalski, and Ono] Let $\mathbf{L}$ be a bounded residuated lattice. The following conditions hold, for all $x, y, z \in L$:

1. $x \rightarrow x = 1, 1 \rightarrow x = x$;

2. $x \le y \implies x \rightarrow y = 1$;

3. $x \rightarrow y \le (z \rightarrow x) \rightarrow (z \rightarrow y)$;
$$
4. x \to y \leq (x \to z) \to (y \to z);
$$

$$
5. x \to (y \to z) = y \to (x \to z) = (x \odot y) \to z;
$$

$$
6. x \odot (x \to y) \leq y, x \leq y \to x;
$$

$$
7. \text{ if } x \leq y \text{ then } y \to z \leq x \to z \text{ and } z \to x \leq z \to y;
$$

$$
8. x \to y \leq (x \odot z) \to (y \odot z);
$$

$$
9. x \odot (y \to z) \leq y \to (x \odot z) \leq (x \odot y) \to (x \odot z).
$$

The residuated lattices are classified with respect to some properties that verify the adjoint
pair of operators. The next definition gives some particular type of residuated lattices.

**Definition 2.2.** [Galatos et al. (2007)Galatos, Jipsen, Kowalski, and Ono] *A bounded residuated lattice L is called:*

1. a **Heyting algebra** if $x \odot y = x \wedge y$ for all $x, y \in L$;

2. an MV-algebra if $(x \to y) \to y = (y \to x) \to x$ for all $x, y \in L$;

3. a BL-algebra if $x \odot (x \to y) = x \wedge y$ and $(x \to y) \vee (y \to x) = 1$ for all $x, y \in L$;

4. an MTL-algebra if $(x \to y) \lor (y \to x) = 1$ for all $x, y \in L$;

5. a *Godel algebra* if it is a BL-algebra for which $x \odot x = x$ for all $x \in L$.

**Definition 2.3.** [Kologani et al. (2019)Kologani, Borzooei, and Kim] *A **Hoop** algebra is algebraic structure $(A; \odot, \to, 1)$ where $(A; \odot, 1)$ is a commutative monoid with unit element 1 and for all $x, y, z \in A$ the following hold:*

$$
1. x \to x = 1;
$$

$$
2. (x \odot y) \to z = x \to (y \to z);
$$

$$
3. x \odot (x \to y) = y \odot (y \to x).
$$

**Definition 2.4.** [Piciu et al. (2021)Piciu, Dan, and Dina] *A non empty subset F of a bounded residuated lattice L is:*

1. A deductive system if:

$$
(a) 1 \in F;
$$

$$
(b) (\forall x, y \in L)(x \wedge x \rightarrow y \in F \implies y \in F).
$$

2. A filter if:

$$
(a) (\forall x, y \in F)(x \leq y, x \in F \implies y \in F);
$$

(b) For all $x, y \in F$, $x \odot y \in F$.
In what follows we give some notions on graphs and directed graphs which can be found e.g,
in [Bang-Jensen and Gutin(2008), Oystein(1962)].

An **undirected graph** $G$ is an ordered pair $(V(G), E(G))$ consisting of a set $V(G)$ of ** vertices (nodes)** and a set $E(G)$ of **edges**, disjoint from $V(G)$, together with an incidence function $\psi_G(\text{relation})$ that associates with each edge an unordered pair of elements of $V(G)$ (not neces- sarily distinct). If $e$ is an edge and $u$ and $v$ are vertices such that $\psi_G(e) = \{u, v\}$, then $e$ is said to join $u$ and $v$, and the vertices $u$ and $v$ are called the ends of $e$. The ends of an edge are said to be **incident** with the edge, and vice versa. Two vertices which are incident with a common edge are **adjacent**, and two distinct adjacent vertices are **neighbours**. The set of neighbours of a vertex $v$ in a graph is denoted by $N(v)$. A graph is a **star graph** if it has a vertex which is adjacent to every other vertex and this is the only adjacency relation.

A **directed graph**, also called **digraph** $D$ is a graph in which the edges have a direction (orien-
tation). A digraph consists of a non-empty set $V(D)$ of elements called vertices and a set $A(D)$ of
ordered pairs of vertices called arcs. We call $V(D)$ the vertex set and $A(D)$ the arc set of $D$. For
an arc $(u, v)$, $u$ is called the **head** and $v$ the **tail**; we also say that $u$ **dominates** $v$ and $v$ **absorbs** $u$. If $x$ is a vertex of $D$, then the **ex-neighborhood** of $x$ is the set $\{z \in V(D) : (x, z) \in A(D)\}$, denoted by $N^+(x)$ and the **in-neighborhood** of $x$ is the set $\{z \in V(D) : (z, x) \in A(D)\}$, denoted by $N^-(x)$. The **out-degree** $d_D^+(x)$ of a vertex $x$ is the number of vertices in $N^+(x)$. A graph is said to be **connected** if, for every partition of its vertex set into two nonempty sets $X$ and $Y$, there is an edge with one end in $X$ and one end in $Y$ otherwise, the graph is **disconnected**. A graph is said to be **simple** if it has no loops or parallel edges. A **complete graph** is a simple graph in which any two vertices are adjacent. A **null graph** is a simple graph in which there are no edges(it consists only of isolated vertices). A **path** is a simple graph whose vertices can be arranged in a linear sequence in such a way that two vertices are adjacent if they are consecutive in the sequence and are nonadjacent otherwise. The **length of a path** is the number of its edges. A **clique** is path with the same ends.

A digraph is called **weakly connected** if for all vertices $v$ and $w$, either $(v, w)$ or $(w, v)$ is
ordered pair. A digraph is said to be **strongly connected** if for all vertices $v$ and $w$, $(v, w)$
and $(w, v)$ are ordered pair. **Strongly connected component** of a digraph is set of vertices in
which there is an arc between any pair of vertices. A **loop** is an arc whose head and tail coincide.
**Parallel** (also called **multiple**) arcs are pairs of arcs with the same tail and the same head
A **tournament** is a directed graph where every pair of distinct vertices are adjacent.

A graph $G$ is called a **star graph** if there is a vertex $x$ in $G$ such that every other vertex in $G$ is connected to $x$ and with no other vertex. A **tree** is a graph which is connected and acyclic (every path has different ends). The **distance** $d(a, b)$ between a pair of vertices $a$ and $b$ is the length of the shortest path between them. The **diameter** of a graph $G$ denoted by $diam(G)$ is defined as the Supremum of the distances between any pair of vertices $u$ and $v$ are said to be **n-branches reachable** if there are $n$ connected nodes between then.

A graph $H$ is called **subgraph** of the graph $M$ if $V(H) \subseteq V(M)$ and the edges(arcs) of $H$ are edges(arc) of $M$.

**Definition 2.5.** [Blumenthal(2019)] Let $D$ be a digraph. A set of vertices $S$ to be dominating in $a$ directed graph $D$ if for every $v \in V(G) - S$ there exists some $v \in S$ such that $(u,v) \in A(D)$
## 3 Digraph on residuated lattices

In this section, we introduce a digraph on bounded residuated lattices and study some properties thereof.

**Definition 3.1.** Let $\mathbf{L}$ be a residuated lattice.

We called $D(L)$ the digraph whose vertices are elements of $L$ and for distinct elements $x, y \in L$, there is an arc from $x$ to $y$ if and only if $x \to y = y$.

**Example 3.1.** Let consider the residuated lattice $\mathbf{L}$ with the universal set $\{0, a, b, c, d, e, f, 1\}$. Lattice ordering is such that $0 \le d \le c \le b \le a \le 1$; $0 \le d \le e \le f \le a \le 1$ and elements $\{b, f\}$ and $\{c, e\}$ are pairwise incomparable. The operations of implication and multiplication are given by the tables:

<table><thead><tr><th>→</th><th>0</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>f</th><th>1</th></tr></thead><tbody><tr><th>0</th><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><th>a</th><td>d</td><td>1</td><td>a</td><td>a</td><td>f</td><td>f</td><td>f</td><td>1</td></tr><tr><th>b</th><td>e</td><td>1</td><td>1</td><td>a</td><td>f</td><td>f</td><td>f</td><td>1</td></tr><tr><th>c</th><td>f</td><td>1</td><td>1</td><td>1</td><td>f</td><td>f</td><td>f</td><td>1</td></tr><tr><th>d</th><td>a</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><th>e</th><td>b</td><td>a</td><td>a</td><td>a</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><th>f</th><td>c</td><td>1</td><td>a</td><td>a</td><td>a</td><td>a</td><td>1</td><td>1</td></tr><tr><th>1</th><td>1</td><td>a</td><td>b</td><td>c</td><td>d</td><td>e</td><td>f</td><td>1</td></tr></tbody></table>

<table><caption>The corresponding digraph in Figure 1.</caption><thead><tr><th>⊙</th><th>0</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>f</th><th>1</th></tr></thead><tbody><tr><th>0</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>a</th><td>0</td><td>c</td><td>c</td><td>c</td><td>0</td><td>d</td><td>d</td><td>a</td></tr><tr><th>b</th><td>0</td><td>c</td><td>c</td><td>c</td><td>0</td><td>0</td><td>d</td><td>b</td></tr><tr><th>c</th><td>0</td><td>c</td><td>c</td><td>c</td><td>0</td><td>0</td><td>0</td><td>c</td></tr><tr><th>d</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>d</td></tr><tr><th>e</th><td>0</td><td>d</td><td>0</td><td>0</td><td>0</td><td>d</td><td>d</td><td>e</td></tr><tr><th>f</th><td>0</td><td>d</td><td>d</td><td>0</td><td>0</td><td>d</td><td>d</td><td>f</td></tr><tr><th>1</th><td>0</td><td>a</td><td>b</td><td>c</td><td>d</td><td>e</td><td>f</td><td>1</td></tr></tbody></table>

<figure><img src="image_1.png" /><figcaption>**Figure 1:** Diraph $D(L)$.</figcaption></figure>

We give a second example.
**Example 3.2.** Let $(\mathbb{Z}_{20}; + , \cdot)$ be the ring of integers modulo 20. Its set of ideals is $\text{Id}(\mathbb{Z}_{20}) = \{I_0, I_1, I_2, I_4, I_5, I_{10}\}$; with $I_i = \frac{i\mathbb{Z}}{20\mathbb{Z}}$ for $i \in \{1, 2, 4, 5, 10\}$ and $I_0 = \frac{20\mathbb{Z}}{20\mathbb{Z}}$.
Defining the operators $I \wedge J = I \cap J$, $I \vee J = I \cup J$, $I \odot J = I \cdot J$ and $I \to J = \{x \in \mathbb{Z}_{20} | x \cdot I \subseteq J\}$; then $\text{Id} = (\text{Id}(\mathbb{Z}_{20}); \vee, \wedge, \odot, \to, I_0, I_1)$ is a bounded residuated lattice. We give table of the implication.

<table><thead><tr><th></th><th>I<sub>0</sub></th><th>I<sub>2</sub></th><th>I<sub>4</sub></th><th>I<sub>5</sub></th><th>I<sub>10</sub></th><th>I<sub>1</sub></th></tr></thead><tbody><tr><th>I<sub>0</sub></th><td>I<sub>1</sub></td><td>I<sub>1</sub></td><td>I<sub>1</sub></td><td>I<sub>1</sub></td><td>I<sub>1</sub></td><td>I<sub>1</sub></td></tr><tr><th>I<sub>2</sub></th><td>I<sub>0</sub></td><td>I<sub>1</sub></td><td>I<sub>4</sub></td><td>I<sub>10</sub></td><td>I<sub>10</sub></td><td>I<sub>1</sub></td></tr><tr><th>I<sub>4</sub></th><td>I<sub>5</sub></td><td>I<sub>1</sub></td><td>I<sub>1</sub></td><td>I<sub>5</sub></td><td>I<sub>5</sub></td><td>I<sub>1</sub></td></tr><tr><th>I<sub>5</sub></th><td>I<sub>4</sub></td><td>I<sub>2</sub></td><td>I<sub>4</sub></td><td>I<sub>1</sub></td><td>I<sub>10</sub></td><td>I<sub>1</sub></td></tr><tr><th>I<sub>10</sub></th><td>I<sub>4</sub></td><td>I<sub>1</sub></td><td>I<sub>4</sub></td><td>I<sub>1</sub></td><td>I<sub>1</sub></td><td>I<sub>1</sub></td></tr><tr><th>I<sub>1</sub></th><td>I<sub>0</sub></td><td>I<sub>2</sub></td><td>I<sub>4</sub></td><td>I<sub>5</sub></td><td>I<sub>10</sub></td><td>I<sub>1</sub></td></tr></tbody></table>

<figure><img src="image_2.png" /><figcaption>Figure 2: $D(\text{Id})$.</figcaption></figure>

The next proposition gives some first properties of the digraph $D(L)$.

**Proposition 3.1.** Let $D(L)$ be a digraph defined on a bounded residuated lattice $L$. The following hold:

1. If $|L| = n$, then $|N^+(1)| = |N^-(1)| = n - 1$.

2. $|N^+(0)| = 1$.

3. If there exist $x, y \in L - \{1\}$ such that $(x, y)$ is an arc, then $D(L)$ has at least one clique.

4. If there exist $x, y \in L - \{1\}$ such that $(x, y)$ and $(y, x)$ are arcs of the digraph, then $D(L)$ has at least one strongly connected component.

5. Any subset of the vertices set containing 1 is a dominating set.

**Proof:** Let $L$ be a bounded residuated lattice and $D(L)$ be the digraph of $L$.

1. Assume that $|L| = n$. $|N^+(1)| = |N^-(1)| = n - 1$ since for all $x \in L\{1\}$, $1 \to x = x$ and $x \to 1 = 1$.
2. By Proposition 2.1 (2), $|N^+(0)| = 1$.

3. Let $x, y \in L - \{1\}$ such that $(x, y)$ is an arc, then the path $1xy1$ form a clique.

4. Let $x, y \in L - \{1\}$ such that there is an arc $(x, y)$, then we have $(1, x), (x, y), (y, 1)$. Hence $\{x, y, 1\}$ is a strongly connected component.

5. This is straightforward from the definition.

□

**Remark 3.1.** 1. The Proposition 3.1 (5) also state that $\{1\}$ is a minimal dominating set and $\{1\}^c$ is the maximal dominating set of the digraph $D(L)$.

2. The dominating number of a graph is the cardinality of minimum dominating set [Oystein(1962)]. It was pointed out in [Vinutha and Arathi(2015)] that the problem of finding that number is NP-hard. This problem is solved for the case of digraph constructed on bounded residuated lattices meaning the algebraic structure from which this graph derived could suggest a simplest way of determining this number.

In the following proposition, we give some properties satisfied by the undirected graph $G(L)$ obtain from the digraph $D(L)$ such that $\{x, y\} \in G(L)$ if $(x, y) \in D(L)$ or $(y, x) \in D(L)$ for a given residuated lattice $L$.

**Proposition 3.2.** If $L$ is a totally ordered bounded residuated lattice, then the following hold:

1. $G(L)$ is a star.

2. $G(L)$ is 1-branching reachable.

**Proof:** Let $L$ be a totally ordered bounded residuated lattice and $D(L)$ be the digraph of $L$.

1. For all $x \in L - \{1\}$, we have the edge $\{1, x\}$. Let $y \in L$ if $x \le y$ then $x \to y = 1 \ne y$; if $y \le x$ then $y \to x = 1 \ne x$. So there is no edge between $x$ and $y$ for all $x, y \in L - \{1\}$. Therefore $G(L)$ is a star.

2. For all $x, y \in L$, we have the edges $\{x, 1\}$ and $\{y, 1\}$. This means that $x$ and $y$ are reachable from the node 1.

□

**Theorem 3.1.** Let $L$ be a bounded residuated lattice, $D(L)$ the digraph of $L$. $G(L)$ is a connected graph and its diameter is at most 2.

**Proof:** Let $x, y \in L$. We have $1 \to x = x$ thus 1 is connected to all the elements of $L$. Hence $G(L)$ is connected.

If $D(L)$ is completed digraph then $\text{diam}(G(L)) = 1$. Else, there exist $x, y \in L$ such that $x \ne y, \{x, y\} \notin E(G(L))$. For all $x, y \in L$ such that $x \ne y$ and $\{x, y\} \notin E(G(L))$, we have $d(x, y) = 2$ because $\{1, x\}$ and $\{1, y\}$ belong to $E(G(L))$. Hence $\text{diam}(G(L)) = 2$.
□ In the next theorem we provide a link between $G(L)$ to the implicative graph from

[Kologani et al. (2019) Kologani, Borzooei, and Kim] constructed on Hoop algebras. In fact there are Hoop algebras which are bounded residuated lattices [Borzooei and Aaly (2020)].

First of all, we recall the definition of an implicative graph of a Hoop algebra. Let $(A; \odot, \to, 1)$ be a Hoop algebra. For any nonempty subset $X$ of $A$, let $r(X) := \{a \in A | x \to a = 1, \forall x \in X\}$.

**Definition 3.2.** [Kologani et al. (2019) Kologani, Borzooei, and Kim] An implicative graph of a Hoop algebra $(A; \odot, \to, 1)$ denoted $\Omega(A)$ is a graph whose vertices are elements of $A$ and for distinct $x, y \in \Omega(A)$, there is an edge connecting $x$ and $y$ if and only if $r(\{x, y\}) = \{1\}$.

Since some bounded residuated lattices are Hoop algebras (in the case the inequalities in Proposition 2.1 (9) are equalities), we can compare $\Omega(L)$ and $G(L)$.

**Theorem 3.2.** Let $L$ be a bounded residuated lattice.

The implicative graph $\Omega(L)$ is a subgraph of the graph $G(L)$.

**Proof:** Let $x, y \in L$ such that $\{x, y\}$ is an edge in the graph $\Omega(L)$.

From the definition of implicative graph, we have $r(\{x, y\}) = \{1\}$. This implies that $x \to 1 = 1$ and $y \to 1 = 1$. From Proposition 2.1 (6), we have $y \le x \to y$, left to prove that $x \to y \le y$.

From Proposition 2.1 (9),

$$ 
\begin{align*}
x \to (y \otimes 1) \le (x \otimes y) \to (x \otimes 1) &\implies x \to y \le (x \otimes y) \to 1, \quad \text{from Proposition 2.1(5)} \\
&\implies x \to y \le y \to (x \to 1) \\
&\implies x \to y \le 1 \to (y \to 1) \\
&\implies (x \to y) \le y.
\end{align*}
$$

Hence $\{x, y\}$ is an edge of the graph $G(L)$. Since $x, y$ are taken arbitrarily in $\Omega(L)$, we conclude that $\Omega(L)$ is a subgraph of $G(L)$. □

**Example 3.3.** Let $L$ be a residuated lattice such that $L = \{0, a, b, c, d, 1\}$, with $0 < a, b < c < 1$; $0 < b < d < 1$, $a, b$ and respective $c, d$ incomparable be a finite residuated lattice. Defined the operations $\odot$ and $\to$ on $L$ by the following tables.

<table><thead><tr><th>→</th><th>0</th><th>a</th><th>b</th><th>c</th><th>d</th><th>1</th></tr></thead><tbody><tr><th>0</th><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><th>a</th><td>d</td><td>1</td><td>d</td><td>1</td><td>d</td><td>1</td></tr><tr><th>b</th><td>c</td><td>c</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><th>c</th><td>b</td><td>c</td><td>d</td><td>1</td><td>d</td><td>1</td></tr><tr><th>d</th><td>a</td><td>a</td><td>b</td><td>c</td><td>1</td><td>1</td></tr><tr><th>1</th><td>1</td><td>a</td><td>b</td><td>c</td><td>d</td><td>1</td></tr></tbody></table>

<table><thead><tr><th>⊗</th><th>0</th><th>a</th><th>b</th><th>c</th><th>d</th><th>1</th></tr></thead><tbody><tr><th>0</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>a</th><td>0</td><td>a</td><td>0</td><td>a</td><td>0</td><td>a</td></tr><tr><th>b</th><td>0</td><td>0</td><td>0</td><td>0</td><td>b</td><td>b</td></tr><tr><th>c</th><td>0</td><td>a</td><td>0</td><td>a</td><td>b</td><td>c</td></tr><tr><th>d</th><td>0</td><td>0</td><td>b</td><td>b</td><td>d</td><td>d</td></tr><tr><th>1</th><td>0</td><td>a</td><td>b</td><td>c</td><td>d</td><td>1</td></tr></tbody></table>

The implicative graph $\Omega(L)$ and the $G(L)$ graph are given below:
<figure><img src="image_3.png" /><figcaption>**Figure 3:** $\Omega(L)$ graph.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Figure 4:** $G(L)$ graph.</figcaption></figure>

# 4 Some properties of residuated lattice based on graphs

Here, we give necessary conditions on the digraph of a residuated lattice that makes this residuated lattice an *MV*-algebra or an *MTL*-algebra.

**Theorem 4.1.** Let $\mathbf{L}$ be a bounded residuated lattice. If $D(L)$ is a strongly connected digraph, then $\mathbf{L}$ is an MV-algebra.

**Proof:** Let $\mathbf{L}$ be a bounded residuated lattice. Assume $D(L)$ is a strongly connected digraph. Then for all $x, y \in L$ we have $(x \to y) \to y = y \to y = 1$ and $(y \to x) \to x = x \to x = 1$. Thus $(x \to y) \to y = (y \to x) \to x$. $\square$

**Remark 4.1.** The digraph of an MV-algebra is not necessary a strongly connected digraph.

For a bounded residuated lattice $\mathbf{L}$, we denote by $D(L^*)$ the digraph from $D(L)$ constructed on $L^* = L - \{0, 1\}$.

**Theorem 4.2.** Let $\mathbf{L}$ be a bounded residuated lattice such that $D(L)$ is a weakly connected digraph. Suppose that for all $x, y \in L$, if $(x, y) \in E(D(L))$ then $\{y, y \to x\}$ are incomparable. If the digraph $D(L^*)$ is a weakly connected, then $\mathbf{L}$ is an MTL-algebra.

**Proof:** Assume $D(L^*)$ is a weakly connected digraph; that is, for all $x, y \in L^*$, either $x \to y = y$ or $y \to x = x$. Let $x, y \in L^*$ if $x \to y = y$, then $(x \to y) \lor (y \to x) = y \lor (y \to x) = 1$, since $y$ and $x \to y$ are incomparable; likewise if $y \to x = x$, then $(x \to y) \lor (y \to x) = (x \to y) \lor y = 1$, since $(x \to y)$ and $x$ are incomparable. $\square$

**Example 4.1.** Let $\mathbf{L}$ be a bounded residuated lattice for which $L = \{0, a, b, c, 1\}$ such that $0 \le a \le 1$; $0 \le b \le 1$; $0 \le c \le 1$. $\{a, b\}$, $\{a, c\}$ and $\{c, b\}$ are incomparable. Define the operations $\odot$ and $\to$ on $L$ as following tables:
<table><tr><td>→</td><td>0</td><td>a</td><td>b</td><td>c</td><td>1</td></tr><tr><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>a</td><td>1</td><td>1</td><td>b</td><td>c</td><td>1</td></tr><tr><td>b</td><td>1</td><td>a</td><td>1</td><td>c</td><td>1</td></tr><tr><td>c</td><td>1</td><td>a</td><td>b</td><td>1</td><td>1</td></tr><tr><td>1</td><td>0</td><td>a</td><td>b</td><td>c</td><td>1</td></tr></table>

<table><tr><td>⊙</td><td>0</td><td>a</td><td>b</td><td>c</td><td>1</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>a</td><td>0</td><td>a</td><td>0</td><td>0</td><td>a</td></tr><tr><td>b</td><td>0</td><td>0</td><td>b</td><td>0</td><td>b</td></tr><tr><td>c</td><td>0</td><td>0</td><td>0</td><td>c</td><td>c</td></tr><tr><td>1</td><td>0</td><td>a</td><td>b</td><td>c</td><td>1</td></tr></table>

The corresponding graph is given below.

<figure><img src="image_5.png" /><figcaption>Figure 5: D(L) graph</figcaption></figure>

**Remark 4.2.** The digraph of an MTL-algebra is not necessary a weakly connected digraph.

**Example 4.2.** Let L be a bounded residuated lattice with $L = \{0, p, q, r, s, 1\}$. The operations $\odot$ and $\to$ on L are given by the tables:

<table><tr><td>→</td><td>0</td><td>p</td><td>q</td><td>r</td><td>s</td><td>1</td></tr><tr><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>p</td><td>s</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>q</td><td>p</td><td>p</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>r</td><td>0</td><td>p</td><td>s</td><td>1</td><td>s</td><td>1</td></tr><tr><td>s</td><td>p</td><td>q</td><td>r</td><td>1</td><td>1</td><td>1</td></tr><tr><td>1</td><td>0</td><td>p</td><td>q</td><td>r</td><td>s</td><td>1</td></tr></table>

<table><tr><td>⊙</td><td>0</td><td>p</td><td>q</td><td>r</td><td>s</td><td>1</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>p</td><td>0</td><td>0</td><td>0</td><td>p</td><td>0</td><td>p</td></tr><tr><td>q</td><td>0</td><td>0</td><td>q</td><td>q</td><td>q</td><td>q</td></tr><tr><td>r</td><td>0</td><td>p</td><td>q</td><td>r</td><td>q</td><td>r</td></tr><tr><td>s</td><td>0</td><td>0</td><td>q</td><td>q</td><td>s</td><td>s</td></tr><tr><td>1</td><td>0</td><td>p</td><td>q</td><td>r</td><td>s</td><td>1</td></tr></table>

$(L; \vee, \wedge, \odot, \to, 0, 1)$ is a MTL-algebra but $D(L)$ is not weakly connected. Because there is not arc between $q$ and $r$ since $r \to q = s$ and $q \to r = 1$.

**Corollary 4.1.** If L in Theorem 4.2 is a BL-algebra, then it is also a Heyting algebra.
In the next proposition, we characterize the dominating set of a strongly connected digraph. Different types of filters of residuated lattice exist in the literature. The notion of MTL-filter was introduced by Zhem [Ma(2012)] but the definition given below comes from Picui [?].

**Definition 4.1.** [?] A filter $F$ is called an MTL-filter if $(x \to y) \lor (x \to y) \in F$ for all $x, y \in F$.

**Proposition 4.1.** Let $\mathbf{L}$ be a residuated lattice. If $D(L)$ is a strongly connected digraph. Then any dominating set of $D(L)$ is an MTL-filter.

**Proof:** Let $A$ be a dominating set of a $D(L)$ digraph. From Proposition 3.1, $1 \in A$.

Let $x, y \in L$ such that $x$ and $x \to y$ are elements of $A$. Then there exists a $\in L$ such that $(x \to y) \to a = a$. Since $y = x \to y$ then $y \to a = a$. Thus $y \in A$. Hence $A$ is a filter.

Furthermore, for all $x, y \in A$, $x \to y = y$ and $y \to x = x$. Thus $(x \to y) \lor (y \to x) = y \lor x$ and $(y \lor x) \to 1 = 1$. Hence $(x \to y) \lor (y \to x) \in A$.

□

**Example 4.3.** In the Example 3.3, the dominating set $F = \{1, d\}$ is an MTL-filter.

# 5 Homomorphisms of a digraph $D(L)$.

Let $\mathbf{L}_1$ and $\mathbf{L}_2$ be bounded residuated lattices, a map $f: L_1 \to L_2$ is a homomorphism of residuated lattices if for all $x, y \in L$ and $\alpha \in \{\wedge, \vee, \odot, \to\}$, $f(x\alpha y) = f(x)\alpha f(y)$ and $f(0) = 0$. Let $D$ and $D'$ be any digraphs. A homomorphism from $D$ to $D'$, written as $f: D \to D'$ is a mapping $f: V(D) \to V(D')$ such that $(f(u), f(v)) \in E(D')$ whenever $(u, v) \in E(D)$.

**Proposition 5.1.** Let $\mathbf{L}$ and $\mathbf{L}'$ be two residuated lattices, $f: L \to L'$ be a map. If $f$ is an homomorphism from $\mathbf{L}$ to $\mathbf{L}'$ then it is a digraph homomorphism from $D(L)$ to $D(L')$.

**Proof:** Let $\mathbf{L}$ and $\mathbf{L}'$ be residuated lattices. Assume that $f: L \to L'$ is homomorphism of residuated lattices and $(a, b) \in E(D(L))$, for $a, b \in L$. Then $a \to b = b$.

$$ 
\begin{align*}
a \to b = b &\implies f(a \to b) = f(b), \\
&\iff f(a) \to' f(b) = f(b), \\
&\iff (f(a), f(b)) \in E(D(L')).
\end{align*}
$$

□

**Example 5.1.** Let $\mathbf{L}$ be a bounded residuated lattice with $L = \{0, a, b, 1\}$ such that $0 \le a \le 1$; $0 \le b \le 1$; $\{a, b\}$ are incomparable. Define the operations $\odot$ and $\to$ on $L$ as follow

<table><tr><td>→</td><td>0</td><td>a</td><td>b</td><td>1</td></tr><tr><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td>a</td><td>c</td><td>1</td><td>c</td><td>1</td></tr><tr><td>c</td><td>a</td><td>a</td><td>1</td><td>1</td></tr><tr><td>1</td><td>0</td><td>a</td><td>c</td><td>1</td></tr></table>

<table><tr><td>⊙</td><td>0</td><td>a</td><td>c</td><td>1</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>a</td><td>0</td><td>a</td><td>0</td><td>a</td></tr><tr><td>c</td><td>0</td><td>0</td><td>c</td><td>c</td></tr><tr><td>1</td><td>0</td><td>a</td><td>c</td><td>1</td></tr></table>
The endomorphism $f : L \to L$ such that $f(0) = 0$; $f(a) = c$; $f(c) = a$; $f(1) = 1$, is a digraph homomorphism.

**Remark 5.1.** The correspondence $D$ which sends every residuated lattice $\mathbf{L}$ to its digraph $D(L)$ extends to a functor from the category $\mathcal{RL}$ of residuated lattices and homomorphisms between them to the category $\mathbf{Drph}$ of digraphs and homomorphisms between them. Using the functor $D$, we can study the class of residuated lattices associated with the same digraph. As first results, we have the following properties.

**Proposition 5.2.** If a bounded residuated lattice $\mathbf{L}$ is such that $D(L)$ is strongly connected, then $\mathbf{L}$ is the unique residuated lattice associated with $D(L)$.

**Proposition 5.3.** Let $\mathbf{L}$ be a bounded residuated lattice. There is not residuated lattice $\mathbf{L}'$ such that $L' \subseteq L$ and $D(L') = D(L)$.

**Proof:** Assume $L' \subseteq L$ and $|L'| = n$, $|L| = m$ with $n < m$. Since 1 is connected to all the elements of $L$ and $L'$, then $N^+(1) = n - 1$ in $D(L')$ and $N^+(1) = m - 1$ in $D(L)$. This means $E(D(L)) \neq E(D(L'))$, therefore $D(L') \neq D(L)$. $\square$ The

next proposition provide some properties of the functor $D$. Recall that a functor is said to be an embedding provided that it is injective on morphisms; it is called a faithful provided that all the hom-set restrictions are injective see [Adámek et al. (1990) Adámek, Herrlich, and Strecker].

**Proposition 5.4.** *The functor *D* is an embedding and faithful functor.*

This follows from Proposition 5.1.

## References

[Adámek et al. (1990) Adámek, Herrlich, and Strecker] J. Adámek, H. Herrlich, and G. Strecker. *Abstract and concrete categories*. Wiley-Interscience, 1990.

[Anderson and Badawi (2008)] D. F. Anderson and A. Badawi. On the zero-divisor graph of a ring. *Communications in Algebra*, 36(8):3073–3092, 2008.

[Banasode and Umathar (2018)] S. Banasode and Y. Umathar. Review of applications of graph theory in engineering. *International Journal of Mathematics Trends and Technology (IJMTT)*, 57(4):225–230, 2018.

[Bang-Jensen and Gutin (2008)] J. Bang-Jensen and G. Z. Gutin. *Digraphs: theory, algorithms and applications*. Springer Science & Business Media, 2008.

[Beck (1988)] I. Beck. Coloring of commutative rings. *Journal of algebra*, 116(1):208–226, 1988.

[Blumenthal (2019)] A. Blumenthal. Independent dominating sets in directed graphs. *arXiv preprint arXiv:1910.05465*, 2019.

[Bondy et al. (1976) Bondy, Murty, et al.] J. A. Bondy, U. S. R. Murty, et al. *Graph theory with applications*, volume 290. Macmillan London, 1976.
[Borzooei and Aaly(2020)] R. Borzooei and M. Aaly. Results on hoops. *Journal of Algebraic Hyperstructures and Logical Algebras*, 1(1):61–77, 2020.

[Galatos et al.(2007)Galatos, Jipsen, Kowalski, and Ono] N. Galatos, P. Jipsen, T. Kowalski, and H. Ono. *Residuated lattices: an algebraic glimpse at substructural logics*. Elsevier, 2007.

[Gan and Yang(2020)] A. Gan and Y. Yang. The zero-divisor graphs of mv-algebras. *Soft Computing*, 24(8):6059–6068, 2020.

[Kologani et al.(2019)Kologani, Borzooei, and Kim] M. A. Kologani, R. A. Borzooei, and H. S. Kim. Graphs based on hoop algebras. *Mathematics*, 7(4):362, 2019.

[Ma(2012)] Z. Ma. Mtl-filters and their characterizations in residuated lattices. *Jisuanji Gongcheng yu Yingyong(Computer Engineering and Applications)*, 48(20):64–66, 2012.

[Oystein(1962)] O. Oystein. *Theory of graphs*. American Mathematical Society, 1962.

[Piciu et al.(2021)Piciu, Dan, and Dina] D. Piciu, C. T. Dan, and A. Dina. Gődel filters in residuated lattices. *Analele ştiinţifice ale Universităţii* "Ovidius" *Constanţa*. *Seria Matematică*, 29(1):183–200, 2021.

[Singh(2014)] R. P. Singh. Application of graph theory in computer science and engineering. *International Journal of Computer Applications*, 104(1), 2014.

[Torkzadeh and Ahmadpanah(2014)] L. Torkzadeh and A. Ahmadpanah. Graph based on residuated lattices. *Journal of Hyperstructures*, 3(1), 2014.

[Vinutha and Arathi(2015)] M. Vinutha and P. Arathi. Graph theory and its applications in computer science and engineering. *International Journal of Engineering and Management Research (IJEMR)*, 5(4):317–319, 2015.