Siti Humaira^∗a , Pudji Astuti^b , Intan Muchtadi-Alamsyah^b , Ahmad Erfanian^c

^aDoctoral Program of Mathematics, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Indonesia

^bAlgebra Research Group, Faculty of Mathematics and Natural Sciences,

Institut Teknologi Bandung, Indonesia

^cDepartment of Pure Mathematics and the Center of Excellence in Analysis on Algebraic Structures, Ferdowsi University of Mashhad, Mashhad, Iran

sitihumaira2610@gmail.com, pudji@itb.ac.id, ntan@itb.ac.id, erfanian@um.ac.ir

The matrix Jacobson graph was introduced in 2019 as a generalization of Jacobson graph and narray Jacobson graph. Let R be a commutative ring and J(R) be the Jacobson radical of the ring R. The matrix Jacobson graph of the ring R of size m × n, denoted by J(R) m×n , is defined as a graph where the vertex set is R^m×ⁿ\J(R) m×n such that two distinct vertices A, B are adjacent if and only if 1 − det(A^tB) is not a unit in the ring R. Here we obtain some graph theoretical properties of J(R) m×n including its connectivity, planarity and perfectness.

Keywords: finite commutative rings, matrix Jacobson graph, connectivity, planarity, perfectness Mathematics Subject Classification : 05C25, 05C40, 05C10, 05C17, 16P10 DOI: 10.5614/ejgta.2022.10.1.12

1. Introduction

The concept of a Jacobson graph of a commutative ring was first introduced by Azimi (2013). Let R be a finite commutative ring. We denote U(R) as the group of units of R and m as a maximal

Received: 9 July 2021, Revised: 11 February 2022, Accepted: 27 February 2022.

^∗Corresponding author.

ideal of R. The Jacobson radical J(R) of R is the intersection of all maximal ideals of R. Jacobson graph of R, denoted by \(\mathfrak{J}_R\), is a graph where the vertex set is \(R \setminus J(R)\) and two distinct vertices x, y are adjacent if \(1 - xy \notin U(R)\) (see [1]). The work of Azimi is further continued for other graph theoretical aspects (see [2],[3],[6],[9]).

Ghayour (2018) generalized the notion of Jacobson graph of a ring to n array Jacobson graph. We denote by \(\mathfrak{J}_R^n\) the graph where the vertex set is the set of column vector of size n in \(R^n \setminus J(R)^n\) and two distinct vertices \(\mathbf{a}\), \(\mathbf{b}\) are adjacent if \(1 - \mathbf{a}^t \mathbf{b} \notin U(R)\). We call this graph the n-array Jacobson graph of R (see [5]).

In this paper, R will stand for a finite commutative ring. We define the notion of a matrix Jacobson graph as an extension of the notions a Jacobson graph and an n-array Jacobson graph. We denote by \(\mathfrak{J}_R^{m\times n}\) the graph having vertex set \(R^{m\times n}\setminus J(R)^{m\times n}\) and two distinct vertices are adjacent if \(1-\det(A^tB)\notin U(R)\). We call this graph the matrix Jacobson graph. As a result, the every n-array Jacobson graph of R can be considered as a matrix Jacobson graph of R of size \(n\times 1\).

For the rest of this note, we consider that the elements of \(R^n\) are in the form of row vectors with entries in R. Note that \(R^n\) is a free R-module of rank n. Let \(\{\dot{e}_1,\ldots,\dot{e}_m\}\) be the standard basis of \(R^m\) and \(\{\mathbf{e}_1,\ldots,\mathbf{e}_n\}\) be the standard basis of \(R^n\). Let \(A \in R^{m \times n}\). Any \(A \in R^{m \times n}\) can be written down as

\[A = (a_{ij}) = I_m \begin{pmatrix} \mathbf{a}_1 \\ \mathbf{a}_2 \\ \vdots \\ \mathbf{a}_m \end{pmatrix} = (\dot{e}_1^t \cdots \dot{e}_m^t) \begin{pmatrix} \mathbf{a}_1 \\ \mathbf{a}_2 \\ \vdots \\ \mathbf{a}_m \end{pmatrix} = \sum_{i=1}^m \dot{e}_i^t \mathbf{a}_i.\]

where \(\mathbf{a}_i = (a_{i1}, a_{i2}, \dots, a_{in}) \in \mathbb{R}^n\).

A local ring is a ring with a unique maximal ideal. A local ring R with maximal ideal \(\mathfrak{m}\) is denoted by \((R.\mathfrak{m})\). It is well known that for a local ring \((R,\mathfrak{m})\), the quotient ring \(R/\mathfrak{m}\) is a field. If a ring has two or more maximal ideals then it is called a non local ring. Let R be a finite non local commutative ring. In this case, the ring R can be decomposed as a direct sum of finite local rings

\[R = R_1 \oplus \cdots \oplus R_k\]

for some local rings \((R_1, \mathfrak{m}_1), \ldots, (R_k, \mathfrak{m}_k)\), \((\mathfrak{m}_i\) is the maximal ideal of \(R_i\)) associated with quotient fields \(F_1, \ldots, F_k\). As a result, the Jacobson radical and unit of R are

\[J(R) = J(R_1) \oplus \cdots \oplus J(R_k)\]

\[U(R) = U(R_1) \oplus \cdots \oplus U(R_k).\]

Further, the matrix over R of size \(m \times n\) can be denoted as

\[R^{m\times n} = R_1^{m\times n} \oplus \cdots \oplus R_k^{m\times n}.\]

Particularly, for \(A \in \mathbb{R}^{m \times n}\), we have

\[A = A_1 \times A_2 \times \cdots \times A_k = \times_{i=1}^k A_i\]

where Aⁱ ∈ R m×n i . For the case m = n, the determinant of A can be written as

\[det(A) = det(\times_{i=1}^k A_i) = \times_{i=1}^k det(A_i).\]

For A, B ∈ R^m×ⁿ , we also have

\[A^{t}.B = \times_{i=1}^{k} (A_{i}^{t}.B_{i}) \text{ and } A + B = \times_{i=1}^{k} (A_{i} + B_{i}).\]

Let F be a field and A ∈ F m×n . An index set of A, denoted by I(A), is defined as a set that contains the indexes of the row vectors of A that form a basis of F n . That is

\[I(A) = \left\{ (j_1, j_2, \dots, j_n) \mid 1 \le j_i < j_{i+1} \le m, \det \left( \sum_{i=1}^n \mathbf{e}_i^t \mathbf{a}_{j_i} \right) \ne 0 \right\}.\] (1)

The aim of this paper is to identify some characteristics of the matrix Jacobson graphs for finite commutative rings. In section 2, we discuss about the connectivity of the graph. In section 3, we characterize the matrix Jacobson graphs which are planar. Finally, we identify rings such that the matrix Jacobson graphs are perfect.

2. Connectivity

One of properties that is usually investigated to understand a graph is the connectivity. In this topic, there are some results concerning Jacobson graphs [1, Theorem 2.2] and the matrix Jacobson graph of fields [10, Theorem 4] that will be utilized to derive our result.

Let R be a finite local commutative ring with maximal ideal m. Let R be the quotient field of R with respect to the maximal ideal m, R = {a| a ∈ R} with a = {a + x| x ∈ m}. Since R is a field, then U(R) = R\0. Let u(R) = {a ∈ R| a ⁻¹ = a} and u 0 (R) = {a ∈ R| a ⁻¹ 6= a}. The vertex set of the square matrix Jacobson graph, J n×n R can be decomposed into

\[V(\mathfrak{J}_R^{n\times n})=V_{\overline{0}}\cup V_{\mathfrak{u}(\overline{R})}\cup V_{\mathfrak{u}'(\overline{R})},\]

with V⁰ = {A ∈ V (J n×n R )|det(A) = 0}, V^u(R) = {A ∈ V (J n×n R )|det(A) ∈ u(R)}, and V^{u 0}(R) = {A ∈ V (J n×n R )|det(A) ∈ u 0 (R)}.

We may write

\[V_{\mathfrak{u}(\overline{R})} = \bigcup_{\overline{x} \in \mathfrak{u}(\overline{R})} V_{\overline{x}},\]

with ∀x ∈ u(R), V^x = {A ∈ V^u(R) |det(A) ∈ x}, and

\[V_{\mathfrak{u}'(\overline{R})} = \bigcup_{\overline{x} \in \mathfrak{u}'(\overline{R})} V_{\overline{x}},\]

\[\text{with } \forall \overline{x} \in \mathfrak{u}'(\overline{R}), V_{\overline{x}} = \{A \in V_{\mathfrak{u}'(\overline{R})} | det(A) \in \overline{x}\}.\]

We generalize the matrix Jacobson graph to the class of local rings by grouping the vertices based on the determinant of its quotient field, as shown in the following theorem.

Theorem 2.1. Let \((R, \mathfrak{m})\) be a local ring. The graph \(\mathfrak{J}_R^{n \times n}\) consists of subgraphs:

• \(|V_{\overline{0}}|\) empty subgraphs,
• \(|\mathfrak{u}(\overline{R})|\) components complete subgraphs, where for any \(\overline{x} \in \mathfrak{u}(\overline{R})\) the set \(V_{\overline{x}}\) forms a complete subgraph.
• \(\frac{|\mathfrak{u}'\overline{R}|}{2}\) components complete bipartite subgraphs, where for any \(\overline{x} \in \mathfrak{u}'(\overline{R})\), the set \(V_{\overline{x}} \cup V_{\overline{x}^{-1}}\) forms a complete bipartite subgraph.

Proof. Let \((R, \mathfrak{m})\) be a local ring.

• Let \(A \in V_0\) with \(det(A) \in \overline{0} = \mathfrak{m}\). Take any \(B \in V(\mathfrak{J}_R^{n \times n})\). Then \(det(A^tB) = det(A^t).det(B) \in \mathfrak{m}\). We obtain \(1 det(A^tB) \in 1 \mathfrak{m}\). Thus \(1 det(A^tB) \in U(R)\). Hence A is an isolated vertex and \(V_0\) has an isolated vertex set in \(\mathfrak{J}_R^{n \times n}\).
• Take \(\overline{x} \in \mathfrak{u}(\overline{R})\). Take \(A, B \in V_{\overline{x}}\). Then \(det(A^tB) \in 1 + \mathfrak{m}\). We have \(1 (det(A^tB)) \in 1 (1 + \mathfrak{m}) = \mathfrak{m}\). So A is adjacent to B. Take any vertex \(C \in V(\mathfrak{J}_R^{n \times n}) \setminus V_{\overline{x}}\). Then \(1 det(A^tC) \notin \mathfrak{m}\). So A is not adjacent to C. Hence \(V_{\overline{x}}\) is a vertex set that forms a complete subgraph \(K_{|V_{\overline{x}}|}\). The number of components of the complete subgraph is \(|\mathfrak{u}(\overline{R})|\).
• Let \(\overline{x} \in \mathfrak{u}'(\overline{R})\). Its inverse is \(\overline{x}^{-1} = \overline{x^{-1}} \in \mathfrak{u}'(\overline{R})\). Take \(X \in V_{\overline{x}}\) and \(Y \in V_{\overline{x}^{-1}}\). Then \(det(X^tY) = det(X^t).det(Y) \in 1+\mathfrak{m}\). We have \(1-det(X^tY) \in \mathfrak{m}\). So X is adjacent to Y. Without loss of generality, take any \(A \in V_{\overline{x}}\) and \(B \in V(\mathfrak{J}_R^{n \times n}) \backslash V_{\overline{x}^{-1}}\), then \(det(A^tB) \notin x^2 + \mathfrak{m}\), so that \(1-det(A^tB) \notin \mathfrak{m}\). So A is not adjacent to B. In other words, we can say that all vertices in \(V_{\overline{x}}\) is only adjacent to \(V_{\overline{x}^{-1}}\), and all vertices in \(V_{\overline{x}^{-1}}\) is only adjacent to \(V_{\overline{x}}\). Hence the set \(V_{\overline{x}} \cup V_{\overline{x}^{-1}}\) forms a complete bipartite subgraph \(K_{|V_{\overline{x}}|,|V_{\overline{x}^{-1}}|}\). The number of its components is \(|\mathfrak{u}'(\overline{R})|/2\).

Based on Theorem 2.1, we can conclude that \(\mathfrak{J}_{\overline{R}}^{n\times n}\) is a subgraph of \(\mathfrak{J}_{R}^{n\times n}\).

Lemma 2.2. Let F be a finite field where |F| = q. The graph \(\mathfrak{J}_F^{n \times n}\) has vertex set \(V(\mathfrak{J}_F^{n \times n}) = F^{n \times n} \setminus 0^{n \times n}\). Let

\[V(\mathfrak{J}_F^{n\times n}) = V_0 \cup V_{U(F)}\]

with \(V_{U(F)} = \{A \in V(\mathfrak{J}_F^{n \times n}) | det(A) \in U(F) \}\). Let

\[V_{U(F)} = \bigcup_{i \in U(F)} V_i,\]

where \(\forall i \in U(F), \ V_i = \{A \in V_{U(F)} | det(A) = i\}.\)Then \(|V(\mathfrak{J}_F^{n \times n})| = q^{n^2} - 1\) consists of

\[|V_0| = q^{n^2} - 1 - \prod_{i=0}^{n-1} (q^n - q^i)\] and \(\forall i \in U(F), |V_i| = \frac{\prod_{i=0}^{n-1} (q^n - q^i)}{q-1}.\)

Proof. First, we obtain that \(|V(\mathfrak{J}_F^{n\times n})|=q^{n^2}-1\) since \(V(\mathfrak{J}_F^{n\times n})=F^{n\times n}\backslash 0^{n\times n}\) and \(|F^{n\times n}|=q^{n^2}\). Second, we will prove that \(|V_{\mathfrak{u}(F)}|=\prod_{i=0}^{n-1}(q^n-q^i)\) so that \(|V_0|=q^{n^2}-1-\prod_{i=0}^{n-1}(q^n-q^i)\). Let \(A\in V_{U(F)}\), with

\[A = \begin{pmatrix} \mathbf{a}_1 \\ \mathbf{a}_2 \\ \vdots \\ \mathbf{a}_n \end{pmatrix}.\]

Then \(det(A) \neq 0\), which implies that the row vector set of A, \(\{\mathbf{a}_1,\dots,\mathbf{a}_n\}\) is a linear independent set. Vector \(\mathbf{a}_1\) is a non zero vector. Since there are \(q^n-1\) non zero vectors in \(F^n\), there are \(q^n-1\) ways to choose \(\mathbf{a}_1\). Assume \(\mathbf{a}_1\) is selected, a non zero vector \(\mathbf{a}_2\) must be linear independent with \(\mathbf{a}_1\), \(\mathbf{a}_2\) must be outside of the subspace \(\langle \mathbf{a}_1 \rangle\). So \(\mathbf{a}_2\) can be chosen from \(q^n-1-q-1=q^n-q\) vectors outside subspace \(\langle \mathbf{a}_1 \rangle\). If \(\mathbf{a}_1,\mathbf{a}_2\) have been chosen, the non zero vector \(\mathbf{a}_3\) must be linear independent with \(\{\mathbf{a}_1,\mathbf{a}_2\}\), so that \(\mathbf{a}_3\) must be outside of the subspace \(\langle \mathbf{a}_1,\mathbf{a}_2 \rangle\). Therefore, we can choose \(q^n-1-q^2-1=q^n-q^2\) vectors outside subspace \(\langle \mathbf{a}_1,\mathbf{a}_2 \rangle\). In the same way we may count the number of ways to choose \(\mathbf{a}_4\) etc. until a non zero vector \(\mathbf{a}_n\) can be chosen from \(q^n-1-q^{n-1}-1=q^n-q^{n-1}\) vectors outside subspace \(\langle \mathbf{a}_1,\dots,\mathbf{a}_{n-1} \rangle\). Hence \(|V_{U(F)}|=\prod_{i=0}^{n-1}(q^n-q^i)\). Since \(V_0=V(\mathfrak{J}_F^{n\times n})\backslash V_{U(F)}, |V_0|=|V(\mathfrak{J}_F^{n\times n})|-|V_{U(F)}|=q^{n^2}-1-\prod_{i=0}^{n-1}(q^n-q^i)\).

Third, we will prove that \(\forall i \in U(F)\), \(|V_i| = \frac{\prod_{i=0}^{n-1} (q^n - q^i)}{q-1}\). Let \(i \in U(F)\). Consider the map

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Note that the mapping \(\lambda_i\) can be considered as a multiplication of any matrix in \(V_1\) by the matrix

\[\lambda_i = \left(\begin{array}{cccc} i & 0 & 0 & \dots & 0 \\ 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ \vdots & \vdots & \dots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & 1 \end{array}\right).\]

Since \(det(\lambda_i) = i \neq 0\), \(\lambda_i\) is an bijective map, so that \(|V_1| = |V_i|\). Based on the second part, we obtain that \(V_{U(F)} = \prod_{i=0}^{n-1} (q^n - q^i)\) and \(V_{U(F)} = \bigcup_{l \in U(F)} V_l\). Then

\[|V_{U(F)}| = \sum_{l \in U(F)} |V_l| = (q-1)|V_1|.\]

Therefore \[|V_l| = \frac{\prod_{i=0}^{n-1} (q^n - q^i)}{q-1}\] with \(l \in U(F)\).

The theorems describing the connectivity of the matrix Jacobson graph of size \(m \times n\) of a field have been discussed in [10, Theorem 6,7]. Let \((R,\mathfrak{m})\) be a local ring with its maximal ideal \(\mathfrak{m}\). Let \(\overline{R}\) be the quotient field of R by the maximal ideal \(\mathfrak{m}\). Let \(A = (a_{ij}) \in R^{m \times n}\). We define \(\overline{A}\) as a matrix with the element \(\overline{a}_{ij} = a_{ij} + \mathfrak{m}\).

Theorem 2.3. Let \((R, \mathfrak{m})\) be a local ring with its maximal ideal \(\mathfrak{m}\). Let \(A, B \in V(\mathfrak{J}_R^{\mathfrak{m} \times n})\) and \(A \neq B\).

• 1. If \(\overline{A} \neq \overline{B}\), then \(\overline{A}\) is adjacent to \(\overline{B}\) if and only if A is adjacent to B.
• 2. If \(\overline{A}\) is not injective, then A is an isolated vertex in \(\mathfrak{J}_R^{m \times n}\).
• 3. If \(\overline{A}\) is injective and \(\overline{A} = \overline{B}\), then \(d(A, B) \leq 2\).

Proof.

• 1. Let \(\overline{A}\) be adjacent to \(\overline{B}\). Then \(\overline{1} det(\overline{A}^t \overline{B}) = \overline{0} = \mathfrak{m}\) if and only if \(1 det(A^t B) \in \mathfrak{m}\). Hence A is adjacent to B.
• 2. Let \(\overline{A}\) be not injective. Take any vertex \(B \in V(\mathfrak{J}_R^{\mathfrak{m} \times n})\). Since \(\overline{A}\) is an isolated vertex in \(\mathfrak{J}_{\overline{R}}^{\mathfrak{m} \times n}\), then \(1 \det(\overline{A}^t \overline{B}) \neq \mathfrak{m}\). Then \(1 \det(A^t B) \in 1 \det(\overline{A}^t \overline{B}) \neq \mathfrak{m}\). Hence A is not adjacent to B. We can conclude that A is an isolated vertex.
• 3. Let \(\overline{A}\) be injective. Write \(\overline{A} = \sum_{i=1}^m \dot{e}_{i}^t \overline{\mathbf{a}}_i\) with \(\{\overline{\mathbf{a}}_{k_1}, \dots, \overline{\mathbf{a}}_{k_n}\}\) is a linear independent set in \(\overline{R}^n\). Since \(\overline{A} = \overline{B}\), we have \(\{\overline{\mathbf{b}}_{k_1}, \dots, \overline{\mathbf{b}}_{k_n}\}\) is a linear independent set. Let \(det(\sum_{i=1}^n \mathbf{e}_{k_i}^t \overline{\mathbf{a}}_{k_i}) = \overline{\alpha}\) with \(\alpha \notin \mathfrak{m}\), then there is an \(m_1 \in \mathfrak{m}\) such that \(det(\sum_{i=1}^n \mathbf{e}_{k_i}^t \mathbf{a}_{k_i}) = \alpha + m_1\). Note that \(det(\sum_{i=1}^n \mathbf{e}_{k_i}^t \mathbf{a}_{k_i}) det(\sum_{i=1}^n \mathbf{e}_{k_i}^t \mathbf{b}_{k_i}) \in \mathfrak{m}\), so there is an \(m_2 \in \mathfrak{m}\) such that \(det(\sum_{i=1}^n \mathbf{e}_{k_i}^t \mathbf{b}_{k_i}) = \alpha + m_2\). If \(\alpha = \alpha^{-1}\) then A is adjacent to B. If \(\alpha \neq \alpha^{-1}\), we can choose \(\{\mathbf{a}'_{k_i}\}_{i=1}^n\) such that \(det(\sum_{i=1}^n \mathbf{e}_{k_i}^t \mathbf{a}'_{k_1}) = \alpha^{-1}\). Therefore,

\[det(A^{t}(\sum_{i=1}^{n} \dot{e}_{k_{i}}^{t} \mathbf{a}_{k_{i}}^{t})) = det(\sum_{i=1}^{n} \mathbf{e}_{k_{i}}^{t} \mathbf{a}_{k_{i}})^{t}.det(\sum_{i=1}^{n} \mathbf{e}_{k_{i}}^{t} \mathbf{a}_{k_{1}}^{t}) = (\alpha + m_{1})\alpha^{-1} \in 1 + \mathfrak{m}.\]

Meanwhile, we also obtain

\[det(B^{t}(\sum_{i=1}^{n} \dot{e}_{k_{i}}^{t} \mathbf{a}_{k_{i}}')) = det(\sum_{i=1}^{n} \mathbf{e}_{k_{i}}^{t} \mathbf{b}_{k_{i}})^{t}.det((\sum_{i=1}^{n} \dot{e}_{k_{i}}^{t} \mathbf{a}_{k_{i}}')) = (\alpha + m_{2})\alpha^{-1} \in 1 + \mathfrak{m}.\]

So

\[A \sim \sum_{i=1}^{n} \dot{e}_{k_i}^t \mathbf{a}_{k_i}' \sim B.\]

Therefore, \(d(A, B) \leq 2\).

Based on the above theorem, we have the following corollary:

Corollary 2.4. Let \((R, \mathfrak{m})\) be a local ring associated with its quotient field of order 2. If \(m \geq 3\), then \(diam((\mathfrak{J}_R^{m \times 2})^*) = 2\).

The next theorem will help us figuring out the form of the matrix Jacobson graph in specific cases.

Theorem 2.5. Let F be a field of order 2. Let \(A, B \in V(\mathfrak{J}_F^{(n+1)\times n})\). The following statements are true:

• 1. If \(|I(A) \cap I(B)|\) is odd, then A is adjacent to B
• 2. If \(|I(A) \cap I(B)|\) is zero or even, then A is not adjacent to B.

Proof. We know that multiplying a matrix by a permutation matrix on the left equals exchange rows according to the permutation. Let \(A, B \in V(\mathfrak{J}_F^{(n+1)\times n})\). Note that \(det(A^tB) = det(A^tP^tPB)\) for any P permutation matrix of size \((n+1)\times(n+1)\). If \(|I(A)\cap I(B)|=k\), then there is a P such that \(I(PA)\cap I(PB)=\{(1,\ldots,n),(2,\ldots,n+1),(1,3,4,\ldots,n+1),\ldots,(1,\ldots,k-2,k,\ldots,n+1)\}\).

Let two distinct vertices in \(V(\mathfrak{J}_F^{(n+1)\times n})\), A,B, where rank(A)=rank(B)=n. We may write \(A=\sum_{i=1}^{n+1}\dot{e}_i^t\mathbf{a}_i\), \(B=\sum_{i=1}^{n+1}\dot{e}_i^t\mathbf{b}_i\). We divide the relation between A and B by two cases: First, let \(I(A)\cap I(B)=\emptyset\). Let \(\{\mathbf{a}_1,\ldots,\mathbf{a}_n\}\) and \(\{\mathbf{b}_1,\ldots,\mathbf{b}_{n-1},\mathbf{b}_{n+1}\}\) be linear independent in \(F^n\). It is clear that if \(\mathbf{a}_{n+1}=0\), then \(A\nsim B\). Since \(I(A)\cap I(B)=\emptyset\), \(\{\mathbf{a}_1,\ldots,\mathbf{a}_{n-1},\mathbf{a}_{n+1}\}\) is linearly dependent. Thus, \(\mathbf{a}_{n+1}=\sum_{i=1}^{n-1}\alpha_i\mathbf{a}_i\), \(\mathbf{b}_n=\sum_{i=1}^{n-1}\beta_i\mathbf{b}_i\) for \(\alpha_i,\beta_i=0\) or \(1,\forall i=1,\ldots,n-1\). We have \(\alpha_i=0\) and \(\beta_i=1\) \(\forall i=1,\ldots,n-1\). Assume that \(\alpha_1,\ldots,\alpha_l=1\) and \(\beta_{l+1},\ldots,\beta_{n-1}=1\) for some \(l\in\{1,\ldots,n-1\}\). Then

\[det(A^{t}B) = det\left(\sum_{i=1}^{n-1} \mathbf{a}_{i}^{t} \mathbf{b}_{i} + \mathbf{a}_{n}^{t} \mathbf{b}_{n} + \mathbf{a}_{n+1}^{t} \mathbf{b}_{n+1}\right)\] \[= det\left(\sum_{i=1}^{n-1} \mathbf{a}_{i}^{t} \mathbf{b}_{i} + \mathbf{a}_{n}^{t} \sum_{i=l+1}^{n-1} \mathbf{b}_{i} + \sum_{i=1}^{l} \mathbf{a}_{i}^{t} \mathbf{b}_{n+1}\right)\] \[= det\left(\begin{pmatrix} \mathbf{a}_{1} \\ \vdots \\ \mathbf{a}_{l} \\ \mathbf{a}_{l+1} \\ \vdots \\ \mathbf{a}_{n-1} \\ \mathbf{a}_{n} \end{pmatrix}^{t} \begin{pmatrix} \mathbf{b}_{1} + \mathbf{b}_{n+1} \\ \vdots \\ \mathbf{b}_{l+1} \\ \vdots \\ \mathbf{b}_{n-1} \\ \mathbf{b}_{l+1} + \cdots + \mathbf{b}_{n-1}. \end{pmatrix}\right)\]

Since \(\{b_{l+1} + \cdots + b_{n-1}\}\) is a linear combination of \(b_{l+1}, \cdots, b_{n-1}\), then \(det(A^tB) = 0\). So A is not adjacent to B.

Second, let \(|I(A) \cap I(B)| = k\) for \(k \in \mathbb{N}\). We may assume that \(\{\mathbf{a}_1, \dots, \mathbf{a}_n\}\) and \(\{\mathbf{b}_1, \dots, \mathbf{b}_n\}\) are independent sets of \(F^n\), and \(\mathbf{a}_{n+1} = \sum_{i=1}^n \alpha_i \mathbf{a}_i\), \(\mathbf{b}_{n+1} = \sum_{i=1}^n \beta_i \mathbf{b}_i\). for \(\alpha_i, \beta_i = 0\) or 1, \(\forall i = 1, \dots, n\). Since \(|I(A) \cap I(B)| = k\), we also may assume \(\alpha_1, \dots, \alpha_{k-1} = 1, \beta_1, \dots, \beta_{k-1} = 1, \alpha_i = 0\) and \(\beta_i = 1 \ \forall i = k, \dots, n\). Hence, assume that \(\alpha_k, \dots, \alpha_l = 1\) and \(\beta_{l+1}, \dots, \beta_n = 1\) for

The matrix Jacobson graph of finite commutative rings Siti Humaira et al.

some \(l \in \{k, \ldots, n\}\). Then

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

From the above equation, if k is odd, then rank(B') = n such that \(det(A^tB) = det(A').det(B') =\)1. Thus \(A \sim B\). If k is even, then rank(B') = n - 1 such that \(det(A^tB) = det(A').det(B') = 0\). Thus \(A \nsim B\).

Example 2.6. Based on Theorem 2.5, we can easily describe the matrix Jacobson graph of size \((n+1) \times n\) over F of order 2 by grouping it into indexes. For example, see the matrix Jacobson graph over \(\mathbb{Z}_2\), \(\mathfrak{J}_{\mathbb{Z}_2}^{3\times 2}\) in Figure 1. There are 7 groups of vertices with different indexes. Let \(A\in\)\(V(\mathfrak{J}_{\mathbb{Z}_2}^{3\times 2})\). If |I(A)|=1,3, the vertices in the same index will form a complete induced subgraph, and if |I(A)| = 2, the vertices in the same index will form an empty induced subgraph.

We generalize the above result on the diameter of the matrix Jacobson graph to the case of non local commutative rings, as shown in the following theorem.

Theorem 2.7. Let R be a non local commutative ring. The following statements about the matrix Jacobson graph of R, \(\mathfrak{J}_{R}^{m \times n}\), are true.

• If m < n, then \(\mathfrak{J}_R^{m \times n}\) is an empty graph,
• If m=n, there are two components consisting of empty subgraphs for every \(A \in V(\mathfrak{J}_R^{n \times n})\)with rank(A) < n and connected subgraphs with \(diam(\mathfrak{J}_{R}^{n \times n})^* \leq 2\),
• If m > n, then there are two components consisting of empty subgraphs for every \(A \in\)\(V(\mathfrak{J}_R^{m \times n})\) with rank(A) < n and connected subgraphs with \(diam(\mathfrak{J}_R^{m \times n})^* \le 4\).

Proof. Let \(R = R_1 \oplus \cdots \oplus R_k\), \(k \geq 2\).

• Let m < n and \(A \in V(\mathfrak{J}_R^{m \times n})\) then A will be isolated because \(\forall C \in V(\mathfrak{J}_R^{m \times n}), \ det(A^tC) =\)0.

Figure 1. graph \(\mathfrak{J}_{\mathbb{Z}_2}^{3\times 2}\)

• Let m=n and \(A\in V(\mathfrak{J}_R^{m\times n})\). In case rank(A)< n, then A is an isolated vertex. In other cases, let \(B\in V(\mathfrak{J}_R^{m\times n}), A\neq B\). If rank(A)=rank(B)=n, then there are \(i,j\in\{1,\ldots,k\}\) such that \(det(A_i)\in U(R_i)\) and \(det(B_j)\in U(R_j)\). If i=j, then

\[A \sim (0 \times \cdots \times A_i^{-1} \times \cdots \times 0) \sim B.\]

If \(i \neq j\), assuming i < j, then

\[A \sim (0 \times \dots \times A_i^{-1} \times \dots \times B_i^{-1} \times \dots \times 0) \sim B.\]

So \(diam(\mathfrak{J}_R^{n\times n})^* \leq 2\).

• Let m > n and \(A \in V(\mathfrak{J}_R^{m \times n})\). If rank(A) < n, then A is isolated. Otherwise, let \(B \in V(\mathfrak{J}_R^{m \times n})\), \(A \neq B\) and for rank(A) = rank(B) = n, then there are i, j such that \(det(A_i) \in U(R_i)\) dan \(det(B_j) \in U(R_j)\).

If i = j, by Theorem 2.3, for \(\overline{A_i} = \overline{B_i}\) then \(d(A_i, B_i) \leq 2\). Obviously \(d(A, B) \leq 2\). For \(\overline{A_i} \neq \overline{B_i}\) then there are \(C_1, C_2, C_3 \in V(\mathfrak{J}_{R_i}^{m \times n})\) thus

\[A_i \sim C_1 \sim C_2 \sim C_3 \sim B_i\].

Hence we have

\[A \sim (0 \times \cdots \times C_1 \times \cdots \times 0) \sim (0 \times \cdots \times C_2 \times \cdots \times 0) \sim (0 \times \cdots \times C_3 \times \cdots \times 0) \sim B.\]

If \(i \neq j\), then there are \(A_i' \in R_i^{m \times n} \setminus J(R_i)^{m \times n}\) such that \(det(A_i^t A_i') = 1\) and \(B_j' \in R_i^{m \times n} \setminus J(R_j)^{m \times n}\) such that \(det(B_j^t B_j') = 1\). Thus

\[A \sim (0 \times \cdots \times A'_i \times \cdots \times Bj' \times \cdots \times 0) \sim B.\]

We conclude that \(diam(\mathfrak{J}_R^{m \times n}) \leq 4\).

3. Planarity

In this section we give conditions when the matrix Jacobson graph is planar. First, we review the planarity of Jacobson graphs. By Theorem of Kuratowski (in [8] or [6, Theorem 5.14]), a graph is planar if and only if there is no subgraph which is a subdivision of \(K_5\) or \(K_{3,3}\).

Theorem 3.1. [1] Let R be a finite ring. Then \(\mathfrak{J}_R\) is planar if and only if either R is a field or R is isomorphic to one of the following rings:

• \(\mathbb{Z}_4\), \(\mathbb{Z}_2 \oplus \mathbb{Z}_2\), \(\mathbb{Z}_2[x]/\langle x^2 \rangle\) of order 4;
• \(\mathbb{Z}_6\) of order 6;
• \(\mathbb{Z}_8\), \(\mathbb{Z}_2 \oplus \mathbb{Z}_4\), \(\mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z}_2\), \(\mathbb{Z}_2[x]/\langle x^3 \rangle\), \(\mathbb{Z}_4[x]/\langle 2x, x^2 \rangle\), \(\mathbb{Z}_2[x]/\langle x^2 + x + 1 \rangle\), \(\mathbb{Z}_4[x]/\langle 2x, x^2 2 \rangle\), \(\mathbb{Z}_2[x, y]/\langle x, y \rangle^2\) of order 8;
• \(\mathbb{Z}_9\), \(\mathbb{Z}_3 \oplus \mathbb{Z}_3\), \(\mathbb{Z}_3[x]/\langle x^2 \rangle\) of order 9.

In the following we extend the above results to the square matrix case \(\mathfrak{J}_R^{n\times n}\) with n>1.

Theorem 3.2. Let R be a finite ring. Then \(\mathfrak{J}_R^{n\times n}\) with n>1 is not planar.

Proof. Let R be a finite ring with \(|R|=q\geq 2\) and \(n\geq 2\). Let \(V_1=\{A\in V(\mathfrak{J}_R^{n\times n})|det(A)=1\}\). By Lemma 2.2 we get

\[|V_1| = \frac{\prod_{i=0}^{n-1} (q^n - q^i)}{q-1} \ge \frac{(q^2 - q^0)(q^2 - q^1)}{q-1} \ge (2^2 - 1)2 = 6.\]

As a result, we obtain a graph \(\mathfrak{J}_R^{n\times n}\), which contains the subgraph \(K_6\). Then, based on Kuratowski theorem, we have \(\mathfrak{J}_R^{n\times n}\) with \(n\geq 2\) is not planar.

Theorem 3.3 ([11]). Let R be a finite ring and \(n \geq 2\). Then \(\mathfrak{J}_R^n\) is planar if and only if

• n=2 and either \(R\cong \mathbb{Z}_2\) or \(\mathbb{Z}_3\); or
• n=3 and \(R\cong \mathbb{Z}_2\).

Theorem 3.4. Let R be a finite ring and \(m > n \ge 2\). Then \(\mathfrak{J}_R^{m \times n}\) is not planar.

Proof. Without loss of generality, we assume that F is a field. For any \(X \in V(\mathfrak{J}_F^{m \times n})\), we may write

\[X = \begin{pmatrix} \mathbf{x}_1 \\ \vdots \\ \mathbf{x}_m \end{pmatrix}\] where for \(i = 1, \dots, m, \mathbf{x}_i \in F^n\).

and

\[I(X) = \left\{ (j_1, j_2, \dots, j_n) \mid 1 \le j_i < j_{i+1} \le m, \det \begin{pmatrix} \mathbf{x}_{j_1} \\ \vdots \\ \mathbf{x}_{j_n} \end{pmatrix} \ne 0 \right\}.\]

Denote by \(U_1 = \{X \in V(\mathfrak{J}_R^{m \times n}) | I(X) = \{(1, 2, ..., n)\}\}\). Let \(A \in U_1\). We may write

\[A = \begin{pmatrix} A' \\ \mathbf{0} \end{pmatrix} = \begin{pmatrix} \mathbf{a}_1 \\ \vdots \\ \mathbf{a}_n \\ 0 \\ \vdots \\ 0 \end{pmatrix}\]

where \(A' \in R^{n \times n}\), \(\mathbf{0} \in 0^{m-n \times n}\). By Lemma 2.2, \(|V_1| \ge 6\), hence \(|U_1| \ge 6\). Since there is \(K_6\) as a subgraph of \(\mathfrak{J}_R^{m \times n}\) with its vertices in \(U_1\). Thus, \(\mathfrak{J}_R^{m \times n}\) with \(m > n \ge 2\) is not planar. \(\square\)

4. Perfectness

Let G be a graph. A clique in G is a maximal complete subgraph and we denote \(\omega(G)\), the number of cliques in G, which is defined as the size of the largest clique in G. A k-vertex coloring of G is an assignment of k colors to the vertices of G such that no two adjacent vertices have the same color and the chromatic number of G is the smallest number k for which G has a k-coloring. A graph G is called perfect if every induced subgraph S of G, the clique number of S is equal to its chromatic number.

Theorem 4.1. [7] (Strong Perfect Graph Theorem) A graph G is perfect if and only if neither G nor complement graph of G contains an induced odd cycle of length > 5.

By using the strong perfect graph theorem above we are able to determine the perfectness of matrix Jacobson graphs. We have \(\mathfrak{J}_R\) is perfect if and only if \(\mathfrak{J}_{R/J(R)}\) is perfect and \(\mathfrak{J}_R^n\) is perfect if and only if \(\mathfrak{J}_{R/J(R)}^n\) is perfect. For the matrix Jacobson graph, we have the following relation.

Lemma 4.2. Let R be a finite local ring. Then \(\mathfrak{J}_R^{m \times n}\) is perfect if and only if \(\mathfrak{J}_{R/J(R)}^{m \times n}\) is perfect.

Proof. \((\Rightarrow)\) By contraposition, let \(\mathfrak{J}^{m\times n}_{\overline{R}}\) be not perfect. Without loss of generality, let the five vertices \(\overline{A}_1, \overline{A}_2, \overline{A}_3, \overline{A}_4, \overline{A}_5\) induce a 5-cycle in \(\mathfrak{J}_R^{m \times n}\). Based on Theorem 2.3 the vertices \(A_1, A_2, A_3, A_4, A_5\) will induce a 5-cycle in \(\mathfrak{J}_R^{m \times n}\). Thus, \(\mathfrak{J}_R^{m \times n}\) is not perfect. (\(\Leftarrow\)) Suppose \(\mathfrak{J}_R^{m \times n}\) is not perfect. Let \(A_1, \ldots, A_k\) induce a k-cycle in \(\mathfrak{J}_R^{m \times n}\) with \(k \geq 5\) and odd. Based on Theorem 2.9 and since \(\mathfrak{J}_R^{m \times n}\) is perfect, \(\overline{A}_i = \overline{A}_j\) for some \(i \neq j\). We obtain:

• • If \(\overline{A}_1 = \overline{A}_2\) and \(\overline{A}_2 \neq \overline{A}_3\), then \(A_1\) adjacent to \(A_3\), contradiction.
  • If \(\overline{A}_1 = \overline{A}_2 = \overline{A}_3 \neq \overline{A}_4\), then \(A_1\) adjacent to \(A_4\) and \(A_2\) adjacent to \(A_4\), contradiction.

• If \(\overline{A}_1 = \overline{A}_3 \neq \overline{A}_2\) then \(A_1\) adjacent to \(A_3\), contradiction.

Hence, \(\overline{A}_1, \ldots, \overline{A}_k\) is a k-cycle.

The result about when the Jacobson graphs and n-array Jacobson graphs are perfect have explained in [1] and [5]. The ring such that the matrix Jacobson graphs are perfect is given in the following theorem.

Theorem 4.3. Let R be a finite local ring. The square matrix Jacobson graph over R, \(\mathfrak{J}_R^{n\times n}\) is a perfect graph.

Proof. We know from Theorem 2.4 that a square matrix Jacobson graph over R consists of an empty subgraph, a complete subgraph, and a complete bipartite subgraph. It is clear that this graph does not have an odd cycle induced subgraph length \(\geq 5\) and neither does the complement. Therefore graph \(\mathfrak{J}_F^{n\times n}\) is a perfect graph.

Theorem 4.4. Let F be a field. The following statements are true:

• 1. If |F| = 2 then
  • \(\mathfrak{J}_F^{3\times2}\) is perfect,
  • for \(n \geq 3\), the graph \(\mathfrak{J}_F^{n+1 \times n}\) is not perfect,
  • \(\bullet\) for m>n+1, the graph \(\mathfrak{J}_F^{m\times n}\) is not perfect.
• 2. If \(|F| \ge 3\), m > n then \(\mathfrak{J}_F^{m \times n}\) is not perfect.
• 3. If \(m \leq n\) then \(\mathfrak{J}_F^{m \times n}\) is perfect.

Proof. 1. Let |F| = 2.

• Let us look at graph \(\mathfrak{J}_F^{3\times 2}\) on Figure 1. There is no k-cycle induced subgraph with k is odd \(\geq 5\). So \(\mathfrak{J}_{\mathbb{Z}_2}^{3\times 2}\) is a perfect graph.
• Let |F|=2 and \(n\geq 3\). Let \(\{\mathbf{a}_1,\ldots,\mathbf{a}_n\}\) be a standard basis of \(F^n\). Then we may choose \(A_1=\sum_{i=1}^n\mathbf{e}_i^t\mathbf{a}_i,\ A_2=\sum_{i=1}^n\mathbf{e}_i^t\mathbf{a}_i+\mathbf{e}_{n+1}^t\mathbf{a}_1,\ A_3=\sum_{i=1}^{n-1}\mathbf{e}_i^t\mathbf{a}_i+\mathbf{e}_n^t\mathbf{a}_1+\mathbf{e}_{n+1}^t\mathbf{a}_3,\ A_4=\mathbf{e}_1^t\mathbf{a}_1+\sum_{i=2}^{n+1}\mathbf{e}_i^t\mathbf{a}_{i-1},\ A_5=\sum_{i=1}^n\mathbf{e}_i^t\mathbf{a}_i+\mathbf{e}_{n+1}^t\mathbf{a}_1+\mathbf{a}_3,\ \text{so that }A_1,\ldots,A_5\) will induce a 5-cycle. Hence graph \(\mathfrak{J}_F^{n+1\times n}\) is not perfect.
• Let m>n+1. Let \(\{\mathbf{a}_1,\ldots,\mathbf{a}_n\}\) be a standard basis of \(F^n\). Then we may choose \(A_1=\sum_{i=1}^n\mathbf{e}_i^t\mathbf{a}_i,\ A_2=\sum_{i=1}^n\mathbf{e}_i^t\mathbf{a}_i+\mathbf{e}_{n+1}^t\mathbf{a}_1,\ A_3=\sum_{i=2}^n\mathbf{e}_i^t\mathbf{a}_i+\mathbf{e}_{n+1}^t\mathbf{a}_1+\mathbf{e}_{n+2}^t\mathbf{a}_2,\ A_4=\sum_{i=3}^n\mathbf{e}_i^t\mathbf{a}_i+\mathbf{e}_{n+1}^t\mathbf{a}_1+\mathbf{e}_{n+2}^t\mathbf{a}_2,\ A_5=\sum_{i=1}^n\mathbf{e}_i^t\mathbf{a}_i+\mathbf{e}_{n+1}^t\mathbf{a}_1+\mathbf{e}_{n+2}^t\mathbf{a}_2,\ \text{so that }A_1,\ldots,A_5\) will induce a 5-cycle. Hence for m>n+1, \(\mathfrak{J}_F^{m\times n}\) is not perfect.
• 2. Let \(\alpha \in F\) with \(\alpha^{-1} = \alpha, \alpha + 1 = 0\). Let \(\{\mathbf{a}_1, \mathbf{a}_2, \dots, \mathbf{a}_n\}\) be a basis of \(F^n\). Then we may choose \(A_1 = \sum_{i=1}^n \dot{e}_i^t \mathbf{a}_i, \ A_2 = \sum_{i=1}^n \dot{e}_i^t \mathbf{a}_i + \dot{e}_{n+1}^t \mathbf{a}_1, \ A_3 = \sum_{i=2}^n \dot{e}_i^t \mathbf{a}_i + \dot{e}_{n+1}^t \mathbf{a}_1, \ A_4 = \alpha \dot{e}_1^t \mathbf{a}_1 + \sum_{i=2}^n \dot{e}_i^t \mathbf{a}_i + \dot{e}_{n+1}^t \mathbf{a}_1, \ A_5 = \sum_{i=1}^n \dot{e}_i^t \mathbf{a}_i + \alpha \dot{e}_{n+1}^t \mathbf{a}_1, \text{ so that } A_1, \dots, A_5 \text{ will induce a 5-cycle. Hence for } m \geq n, \mathfrak{J}_F^{m \times n} \text{ is not perfect.}\)

Figure 2. graph \(\mathfrak{J}^{n\times n}_{\mathbb{Z}_2\oplus\mathbb{Z}_2}, \mathfrak{J}^{n\times n}_{\mathbb{Z}_3\oplus\mathbb{Z}_2}\) and \(\mathfrak{J}^{n\times n}_{\mathbb{Z}_3\oplus\mathbb{Z}_3}\)

3. If m < n and since graph \(\mathfrak{J}_F^{m \times n}\) is the empty graph, then neither \(\mathfrak{J}_F^{m \times n}\) nor complement of \(\mathfrak{J}_F^{m \times n}\) contain an induced odd cycle of length \(\geq 5\). We have \(\mathfrak{J}_F^{m \times n}\) is perfect. If m = n then by Theorem 2.1 the components of graph \(\mathfrak{J}_F^{n \times n}\) contain an empty subgraph, two complete subgraphs and complete bipartite graphs such that \(\mathfrak{J}_F^{n \times n}\) is perfect.

Let \(R = R_1 \oplus \cdots \oplus R_k\), \(k \geq 2\). For any \(i \in \{1, \dots, k\}\) and \(q_i \in R_i\), define \(X_{q_i} = \{A \in R_i^{n \times n} | det(A) = q_i\}\). Using these notations, for any \(A = \times_{i=1}^k A_i\) we have \(A_j \in X_{q_j}\) for some \(q_j \in R_j\). In this case, we denote \(A \in (X_{q_1}, \dots, X_{q_k})\).

Theorem 4.5. Let \(R = R_1 \oplus \cdots \oplus R_k\), \(k \geq 2\) be a non local ring. The matrix Jacobson graph of R, \(\mathfrak{J}_R^{m \times n}\), is perfect if and only if m < n or m = n and

• 1. for k = 2, \(R \cong R_1 \oplus R_2\) with \(|R_1|, |R_2| < 4\) and \(R_i\) is a field,
• 2. for k = 3, \(R \cong \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z}_2\) or \(R \cong \mathbb{Z}_3 \oplus \mathbb{Z}_2 \oplus \mathbb{Z}_2\)
• 3. for k = 4, \(R \cong \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z}_2\)

Proof. • Let m < n. Since \(\mathfrak{J}_R^{m \times n}\) is an empty graph and its complement is a complete graph, it is obvious that this graph is perfect.

• Let m=n. We divide this into four cases, k=2, k=3, k=4, and \(k \ge 5\).
  • 1. Case k=2. Let \(R\cong R_1\oplus R_2\). Assume that \(R=\mathbb{Z}_5\oplus \mathbb{Z}_5\). Choose \((X_1,X_2)\), \((X_1,X_4)\), \((X_4,X_4)\), \((X_4,X_2)\), \((X_2,X_3)\) such that a 5-cycle will be induced in \(\mathfrak{J}_{\mathbb{Z}_5\oplus\mathbb{Z}_5}^{n\times n}\). So \(R\cong R_1\oplus R_2\) is not perfect for \(|R_i|\geq 5\). If \(|R_1|,|R_2|<5\), we may calculate for \(R\cong \mathbb{Z}_2\oplus \mathbb{Z}_2,\mathbb{Z}_3\oplus \mathbb{Z}_2,\mathbb{Z}_3\oplus \mathbb{Z}_3,\mathbb{Z}_2[x]/\langle x^2+x+1\rangle\oplus \mathbb{Z}_2,\mathbb{Z}_2[x]/\langle x^2+x+1\rangle\oplus \mathbb{Z}_3,\mathbb{Z}_2[x]/\langle x^2+x+1\rangle\oplus \mathbb{Z}_2[x]/\langle x^2+x+1\rangle\) in Figure 2, Figure 3 and Figure 4. such that this graph is perfect.
  • 2. Case k=3. We will show that \(\mathfrak{J}_R^{n\times n}\) for k=3 except for the case \(R\cong \mathbb{Z}_2\oplus \mathbb{Z}_2\oplus \mathbb{Z}_2\) and \(R\cong \mathbb{Z}_3\oplus \mathbb{Z}_2\oplus \mathbb{Z}_2\), it is not perfect. Assume that \(R=\mathbb{Z}_3\oplus \mathbb{Z}_3\oplus \mathbb{Z}_2\). Then, we choose five vertices where each vertex is in the following sets: \((X_2,X_2,X_0)\), \((X_2,X_1,X_0)\),

Figure 3. graph J n×n Z2[x]/hx2+x+1i⊕Z² and J n×n Z2[x]/hx2+x+1i⊕Z³

Figure 4. graph J n×n Z2[x]/hx2+x+1i⊕Z2[x]/hx2+x+1i

Figure 5. graph \(\mathfrak{J}_{\mathbb{Z}_2 \times \mathbb{Z}_2 \times \mathbb{Z}_2}^{n \times n}\)

\((X_0,X_1,X_1), (X_1,X_0,X_1), (X_1,X_2,X_0)\) such that a 5-cycle is induced. So for \(R\cong R_1\oplus R_2\oplus R_3\) for \(|R_1|, |R_2|>2\) and \(|R_3|>1\), the graph is not perfect. Otherwise, for \(R\cong \mathbb{Z}_2\oplus \mathbb{Z}_2\oplus \mathbb{Z}_2\) or \(R\cong \mathbb{Z}_3\oplus \mathbb{Z}_2\oplus \mathbb{Z}_2\) the longest cycle of graph \(\mathfrak{J}_R^{n\times n}\) is four. Then \(\mathfrak{J}_{F_2\oplus F_2\oplus F_2}^{n\times n}\) and \(\mathfrak{J}_{F_3\oplus F_2\oplus F_2}^{n\times n}\) is perfect. (see Figure 5 and Figure 6)

• 3. Case k=4. We will show that \(\mathfrak{J}_R^{n\times n}\) for k=4 except \(R\cong\mathbb{Z}_2\oplus\mathbb{Z}_2\oplus\mathbb{Z}_2\oplus\mathbb{Z}_2\oplus\mathbb{Z}_2\), is not perfect. Assume that \(R=\mathbb{Z}_3\oplus\mathbb{Z}_2\oplus\mathbb{Z}_2\oplus\mathbb{Z}_2\oplus\mathbb{Z}_2\oplus\mathbb{Z}_2\). Then choose five vertices where each vertex is in the following sets: \((X_2,X_1,X_0,X_0), (X_2,X_0,X_1,X_0), (X_0,X_0,X_1,X_1), (X_1,X_0,X_0,X_1), (X_1,X_1,X_0,X_0)\), such that a 5-cycle is induced. So for \(R\cong R_1\oplus R_2\oplus R_3\oplus R_4\) with \(|R_i|>2,\ i=1,\ldots,4\), the graph is not perfect. Otherwise, for \(R\cong\mathbb{Z}_2\oplus\mathbb{Z}_2\oplus\mathbb{Z}_2\oplus\mathbb{Z}_2\oplus\mathbb{Z}_2\) the longest cycle of graph \(\mathfrak{J}_R^{n\times n}\) is four. So \(\mathfrak{J}_{\mathbb{Z}_2\oplus\mathbb{Z}_2\oplus\mathbb{Z}_2\oplus\mathbb{Z}_2\oplus\mathbb{Z}_2}^{n\times n}\), the graph is perfect.
• 4. Case \(k \geq 5\). We will show for \(R = R_1 \oplus \cdots \oplus R_k\), the graph is not perfect. Assume that \(R = \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z}_2\). Then choose five vertices in \(\mathfrak{J}_{\mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z}_2 \oplus \mathbb{Z}_2}^{n \times n}\) where each vertex is in the following sets: \((X_1, X_1, X_0, X_0, X_0)\), \((X_1, X_0, X_1, X_0, X_1, X_0, X_0)\), \((X_0, X_1, X_0, X_1, X_0, X_1, X_0, X_1, X_0)\), such that a 5-cycle is induced. We obtain for \(R = R_1 \oplus \cdots \oplus R_k\) with \(|R_i| \geq 2\), \(i = 1, \ldots, k\), the graph is also not perfect.
• Let m > n. We obtain that graph \(\mathfrak{J}_{\mathbb{Z}_2 \oplus \mathbb{Z}_2}^{m \times n}\) is not perfect as a result of the induced 5-cycle in \(\mathfrak{J}_{\mathbb{Z}_2 \oplus \mathbb{Z}_2}^{3 \times 2}\), as shown in Figure 7. This approach can be generalized to any ring R. Thus for m > n, \(\mathfrak{J}_R^{m \times n}\) is not perfect.

5. Concluding Remarked

To better understand the structure and properties of the matrix Jacobson graphs, investigations of other properties of this class of graphs, such as the properties of the chromatic number, girth,

Figure 6. graph J n×n Z3×Z2×Z²

Figure 7. induced 5-cycle in J 3×2 Z2⊕Z²

path, cycle, and matching are currently being carried out.

Acknowledgement

This work has been supported by the PMDSU Grant, Ministry of Education, Culture, Research and Technology, Indonesia.

References

• [1] A. Azimi, A. Erfanian, and M. Farrokhi D.G., The Jacobson graph of commutative rings, J. Algebra Appl. 12 (3) (2013), 1250179.
• [2] A. Azimi, A. Erfanian, and M. Farrokhi D.G., Isomorphisms between Jacobson graphs, Rend. Circ. Mat. Palermo 63 (2) (2014), 277–286.
• [3] A. Azimi and M. Farrokhi D.G., Cycles and paths in Jacobson graphs, Ars Combin 134 (2017), 61–74.
• [4] B.R. McDonald, Finite rings with Identity, New York: Marcel Dekker Inc (1974)
• [5] H. Ghayour, A. Erfanian, A. Azimi, and M. Farrokhi D.G., n-array Jacobson graphs, The Iranian Mathematical Society, Iran 43 (7) (2017), 2137–2152.
• [6] H. Ghayour, A. Erfanian, and A. Azimi, Some result on the Jacobson graph of a commutative ring, Rend. Circ. Mat. Palermo 67 (1) (2018), 33–41.
• [7] M.Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann. Math. (2), 162 (1) (2006), 51–229.
• [8] K. Kuratowski, Sur le probleme des courbes gauches en topologie, Fund. Math., ` 15 (1930), 271–283.
• [9] S. Akbari, S. Khojasteh, and A. Yousefzadehfard, The proof of a conjecture in Jacobson graph of commutative ring, J.Algebra Appl. 14 (10) (2015), 1550107.
• [10] S. Humaira, P. Astuti, I. Muchtadi-Alamsyah, and A. Erfanian, The matrix Jacobson graph of fields, J. Phys.: Conf. Ser. 1538 (1) (2020), 012008.
• [11] Z. Fattahi, A. Erfanian, and M. Alinejad, Some new results on Jacobson graphs, Rend. Circ. Mat. Palermo 68 (1) (2019), 129–137.