Mehrdad Nasernejad

Univ. Artois, UR 2462, Laboratoire de Mathematique de Lens (LML), F-62300 Lens, France. ´ orcid.org/0000-0003-1073-1934

m nasernejad@yahoo.com

Suppose that V = {1, . . . , n} is a non-empty set of n elements, S = {S1, . . . , Sm} a non-empty set of m non-empty subsets of V . In this paper, by using some algebraic notions in commutative algebra, we investigate the question arises whether there exists an undirected finite simple graph G with V (G) = V , where S is the set whose elements are the minimal dominating sets of G.

Keywords: minimal dominating sets, regular graphs, closed neighborhood ideals, dominating ideals Mathematics Subject Classification : 13B25, 05C25, 13F20, 05E40 DOI: 10.5614/ejgta.2023.11.2.5

1. Introduction

In general, monomial ideals play an important role in investigating the relation between combinatorics and commutative algebra. Indeed, the relation between these two fields permit us to use techniques and methods in commutative algebra to explore combinatorial problems, and vice versa. Thus, commutative algebraists have started studying the properties of finite simple graphs through monomial ideals. One of the pioneers in this area was Villarreal [11] which introduced the notion of edge ideals. Let G = (V (G), E(G)) be a finite simple graph on the vertex set V (G) = {1, . . . , n}, that is, G has no loops and no multiple edges. Moreover, assume that R = K[x1, . . . , xn] is a polynomial ring over a field K in n variables. Then we can build the edge ideal I(G) ⊂ K[x1, . . . , xn] which is generated by all monomials xix^j such that {i, j} ∈ E(G). In addition, the vertex cover

Received: 31 August 2022, Revised: 17 June 2023, Accepted: 25 July 2023.

ideal of G, denoted by J(G), is generated by monomials that correspond to vertex covers of G, where a vertex cover means a set of vertices that contains at least one vertex from each edge. It should be noted that J(G) is the Alexander dual of I(G), that is, J(G) = I(G) ∨ .

More recently, in [10], Sharifan and Moradi introduced the notions of closed neighborhood ideals and dominating ideals of graphs. Refer to Section 2 for these definitions. In particular, in [10], the authors studied regularity and projective dimension of closed neighborhood ideals and dominating ideals in terms of the information from the underlying graph. After that, in [3], Honeycutt and Sather-Wagstaff probed the Cohen-Macaulay, unmixed, and complete intersection properties of closed neighborhood ideals. Next, in [9, 7], the authors concentrated on the normality, strong persistence property, persistence property, and symbolic strong persistence property of closed neighborhood ideals and dominating ideals of some classes of graphs.

Besides these papers, another motivation of this paper originates from [4, 8]. In fact, in [4], the author argued on the sets defining minimal vertex covers of graphs, while, in [8], the authors studied the sets defining minimal vertex covers of uniform hypergraphs. In this paper, we discuss the sets defining minimal dominating set of graphs. Indeed, suppose that V = {1, . . . , n} is a non-empty set of n elements, S = {S1, . . . , Sm} a non-empty set of m non-empty subsets of V . Our aim is to investigate the question arises whether there exists an undirected finite simple graph G with V (G) = V , where S is the set whose elements are the minimal dominating sets of G. To answer this question, we focus on regular graphs (cf. Theorem 3.1).

Throughout this paper, we denote the unique minimal set of monomial generators of a monomial ideal I by G(I). Furthermore, all graphs are finite, simple, and undirected.

2. Preliminaries

In this section, we state the definitions which we will use in the rest of this paper. For any unexplained notation and terminology, we refer the reader to [1, 2, 5, 6, 12, 13].

We begin with the definition of associated primes of an ideal in a commutative Noetherian ring. Suppose that R is a commutative Noetherian ring and I an ideal of R. A prime ideal p ⊂ R is an associated prime of I if there exists an element v in R such that p = (I :^R v), where (I :^R v) = {r ∈ R | rv ∈ I}. The set of associated primes of I, denoted by AssR(R/I), is the set of all prime ideals associated to I. In particular, if I = Q¹ ∩ · · · ∩ Q^m is a minimal primary decomposition of I, then AssR(R/I) = {p1, . . . , pm}, where pⁱ = √ Qⁱ for all i = 1, . . . , m.

In what follows, we focus on the definitions of closed neighborhood ideals and dominating ideals. Let G be a finite simple graph with the vertex set V (G) and the edge set E(G). The closed neighborhood of a vertex v ∈ V (G) is NG[v] = {u | {u, v} ∈ E(G)} ∪ {v}. Due to [10], the closed neighborhood ideal of G, denoted by NI(G), has been defined as

\[NI(G) = (\prod_{j \in N_G[i]} x_j : i \in V(G)).\]

A subset S ⊆ V (G) is called a dominating set of G if S ∩ NG[v] ̸= ∅ for any v ∈ V (G). Also, S is called a minimal dominating set of G if it is a dominating set of G and no proper subset of S is

a dominating set of G. By virtue of [10], the dominating ideal of G has been defined as

\[DI(G) = (\prod_{i \in S} x_i : S \text{ is a minimal dominating set of } G).\]

Recall that if u = x a1 1 · · · x an n is a monomial in a polynomial ring R = K[x1, . . . , xn], then the support of u is given by supp(u) := {xⁱ | aⁱ > 0}. It should be noted that for any square-free monomial ideal I ⊂ R = K[x1, . . . , xn], the Alexander dual of I, denoted by I ∨ , is given by

\[I^{\vee} = \bigcap_{u \in \mathcal{G}(I)} (x_i : x_i \in \text{supp}(u)).\]

On account of [10, Lemma 2.2], we have DI(G) is the Alexander dual of NI(G), that is, DI(G) = NI(G) ∨ .

3. Main result

Suppose that V = {1, . . . , n} is a non-empty set of n elements, S = {S1, . . . , Sm} a non-empty set of m non-empty subsets of V . In this section, we investigate the question arises whether there exists an undirected finite simple graph G with V (G) = V , where S is the set whose elements are the minimal dominating sets of G.

Before asserting the main result of this section, one needs to review the following defnitions. Remember that an m × n matrix M = (aij ) is called binary if aij ∈ {0, 1} for each i = 1, . . . , m and j = 1, . . . , n.

Definition 3.1. Let M = (aij ) be an m × n binary matrix, and r be a positive integer with 2 ≤ r ≤ n. We say that M satisfies the condition:

• (i) when, for any 1 ≤ i1, i² ≤ m with i¹ ̸= i2, there exists a positive integer 1 ≤ j ≤ n such that aⁱ1,j > aⁱ2,j .
• (ii) when, for any r − 1 distinct positive integers 1 ≤ j1, . . . , jr−¹ ≤ n, there exists a positive integer 1 ≤ i ≤ m such that ai,j¹ + · · · + ai,jr−¹ = 0.
• (iii) when, for any ℓ ≥ r distinct positive integers 1 ≤ j1, . . . , j^ℓ ≤ n such that ai,j¹ +· · ·+ai,j^ℓ ≥ 1 for all i = 1, . . . , m, then there exist at least r distinct integers j^α1 , . . . , j^αr ∈ {j1, . . . , jℓ} such that ai,jα¹ + · · · + ai,jαr ≥ 1 for all i = 1, . . . , m.
• (iv) when, there exist n subsets (possibly some of them are the same) Γ^t := {θt,1, . . . , θt,r} ⊆ {1, . . . , n} for any integer 1 ≤ t ≤ n such that we have
  • (a) ai,θt,1+· · ·+ai,θt,r ≥ 1 fori = 1, . . . , m and t = 1, . . . , n. Furthermore, if z1, . . . , z^r are r distinct integers such that ai,z¹ +· · ·+ai,z^r ≥ 1 for i = 1, . . . , m, then {z1, . . . , zr} = Γ^s for some 1 ≤ s ≤ n;
  • (b) for any integer 1 ≤ t ≤ n there exist r sets Γⁱ¹ , . . . , Γ^ir with t ∈ Γ^ik for all k = 1, . . . , r;

• (c) \(t \in \Gamma_t\) for \(t = 1, \ldots, n\);
• (d) \(\theta_{t,i} \in \Gamma_t\) if and only if \(t \in \Gamma_{\theta_{t,i}}\) for i = 1, ..., r and t = 1, ..., n, which ensures us that the resulting graph is not directed.

Definition 3.2. Suppose that \(V = \{1, ..., n\}\) is a non-empty set of n elements, and let \(S = \{S_1, ..., S_m\}\) be a non-empty set of m subsets of V. We define the incidence matrix associated to S, denoted by M(S), as the binary matrix \(M(S) = (a_{ij})\) with m rows and n columns such that \(a_{ij} = 0\) if \(j \notin S_i\), and \(a_{ij} = 1\) if \(j \in S_i\) for all i = 1, ..., m and j = 1, ..., n.

We are ready to state the main result of this paper in the following theorem.

Theorem 3.1. Suppose that \(V = \{1, ..., n\}\) is a non-empty set of n elements, \(S = \{S_1, ..., S_m\}\) a non-empty set of m non-empty subsets of V, and \(1 \le r \le n\) a positive integer. Then there exists an undirected (r-1)-regular graph G with G with G is the set whose elements are the minimal dominating sets of G if and only if the matrix G is a satisfies conditions (i)-(iv).

If there exists such (r-1)-regular graph G, then the closed neighborhood ideal of G is given by

\[NI(G) = (x_{j_1} \cdots x_{j_r} : a_{i,j_1} + \cdots + a_{i,j_r} \ge 1 \text{ for all } i = 1, \dots, m,\]
with \(j_1, \dots, j_r\) are distinct positive integers).

Proof. To establish the forward implication, assume there exists an (r-1)-regular graph G with V(G)=V, where \(\mathcal S\) is the set whose elements are the minimal dominating sets of G. We show that \(M(\mathcal S)\) satisfies Condition (i). On the contrary, assume that Condition (i) does not hold. So there exist \(1 \le i_1, i_2 \le m\) with \(i_1 \ne i_2\) such that \(a_{i_1,j} \le a_{i_2,j}\) for each \(j=1,\ldots,n\). Hence, we get \(S_{i_1} \subseteq S_{i_2}\), which contradicts the minimality of \(S_{i_2}\). Accordingly, we conclude that \(M(\mathcal S)\) satisfies Condition (i).

We prove that \(M(\mathcal{S})\) satisfies Condition (ii). On the contrary, assume that there exist r-1 distinct positive integers \(1 \leq j_1, \ldots, j_{r-1} \leq n\), such that \(a_{i,j_1} + \cdots + a_{i,j_{r-1}} \neq 0\) for each \(1 \leq i \leq m\). To simplify the notation, put \(\mathfrak{p}_i := (x_w : w \in S_i)\) for each \(i=1,\ldots,m\). Due to \(S_1,\ldots,S_m\) are the minimal dominating sets of G, [10, Lemma 2.2] implies that \(NI(G) = \bigcap_{i=1}^m \mathfrak{p}_i\), where NI(G) denotes the closed neighborhood ideal of G. The assumption gives that \(\{j_1,\ldots,j_{r-1}\}\cap S_i \neq \emptyset\) for each \(i=1,\ldots,m\). Hence, one can conclude that \(\{x_{j_1},\ldots,x_{j_{r-1}}\}\cap \mathfrak{p}_i \neq \emptyset\) for each \(i=1,\ldots,m\). This yields that \(x_{j_1}\cdots x_{j_{r-1}}\in \mathfrak{p}_i\) for each \(i=1,\ldots,m\), and so \(x_{j_1}\cdots x_{j_{r-1}}\in \cap_{i=1}^m \mathfrak{p}_i\). Thus, there exists an element \(u\in \mathcal{G}(NI(G))\) such that \(u\mid x_{j_1}\cdots x_{j_{r-1}}\). So \(\deg u\leq r-1\). On the other hand, since G is an (r-1)-regular graph, one obtains \(\deg u=r\), which is a contradiction.

Here, we demonstrate that \(M(\mathcal{S})\) satisfies Condition (iii). Suppose that for each \(\ell \geq r\) distinct positive integers \(1 \leq j_1, \ldots, j_\ell \leq n\), we have \(a_{i,j_1} + \cdots + a_{i,j_\ell} \geq 1\) for all \(i = 1, \ldots, m\). Want to show that there are at least r distinct integers \(j_{\alpha_1}, \ldots, j_{\alpha_r} \in \{j_1, \ldots, j_\ell\}\) such that \(a_{i,j_{\alpha_1}} + \cdots + a_{i,j_{\alpha_r}} \geq 1\) for all \(i = 1, \ldots, m\). Set \(\mathfrak{p}_i := (x_w : w \in S_i)\) for each \(i = 1, \ldots, m\). It is not hard to see that \(a_{i,j_1} + \cdots + a_{i,j_\ell} \geq 1\) for all \(i = 1, \ldots, m\), if and only if \(\{j_1, \ldots, j_\ell\} \cap S_i \neq \emptyset\) for all \(i = 1, \ldots, m\), if and only if \(\{x_{j_1}, \ldots, x_{j_\ell}\} \cap \mathfrak{p}_i \neq \emptyset\) for all \(i = 1, \ldots, m\), if and only if \(x_{j_1} \cdots x_{j_\ell} \in \mathfrak{p}_i\) for all \(i = 1, \ldots, m\). This leads to \(x_{j_1} \cdots x_{j_\ell} \in \cap_{i=1}^m \mathfrak{p}_i\). On account of \(NI(G) = \cap_{i=1}^m \mathfrak{p}_i\) and G is an (r-1)-regular graph, this implies that there exists an element \(u \in \mathcal{G}(NI(G))\) with \(\deg u = r\)

such that \(u \mid x_{j_1} \cdots x_{j_\ell}\). Let \(u = x_{j_{\alpha_1}} \cdots x_{j_{\alpha_r}}\). Accordingly, we get \(j_{\alpha_1}, \dots, j_{\alpha_r} \in \{j_1, \dots, j_\ell\}\). One can derive from \(u \in \mathcal{G}(NI(G))\) that \(x_{j_{\alpha_1}} \cdots x_{j_{\alpha_r}} \in \mathfrak{p}_i\) for all \(i = 1, \dots, m\). Therefore, \(a_{i,j_{\alpha_1}} + \dots + a_{i,j_{\alpha_r}} \geq 1\) for all \(i = 1, \dots, m\), as claimed.

To finish the argument, we show that \(M(\mathcal{S})\) satisfies Condition (iv). By virtue of G is an (r-1)-regular graph, this implies that there exist n subsets \(N_G[1],\ldots,N_G[n]\) such that, for each \(t=1,\ldots,n\), \(N_G[t]\) as the closed neighborhood of the vertex \(t\in V(G)\) has r elements. Set \(N_G[t]:=\{\theta_{t,1},\ldots,\theta_{t,r}\}\) for each \(t=1,\ldots,n\). It follows from the definition of closed neighborhood ideal of G that \(NI(G)=(x_{\theta_{t,1}}\cdots x_{\theta_{t,r}}:t=1,\ldots,n)\). Since \(NI(G)=\cap_{i=1}^m\mathfrak{p}_i\), where \(\mathfrak{p}_i=(x_w:w\in S_i)\) for each \(i=1,\ldots,m\), this gives that \(x_{\theta_{t,1}}\cdots x_{\theta_{t,r}}\in\mathfrak{p}_i\) for each \(i=1,\ldots,m\) and \(t=1,\ldots,n\). Fix \(1\leq t\leq n\). Hence, we get \(\{\theta_{t,1},\ldots,\theta_{t,r}\}\cap S_i\neq\emptyset\) for each \(i=1,\ldots,m\), and so \(a_{i,\theta_{t,1}}+\cdots+a_{i,\theta_{t,r}}\geq 1\) for each \(i=1,\ldots,m\). Now, assume that \(z_1,\ldots,z_r\) are r distinct integers such that \(a_{i,z_1}+\cdots+a_{i,z_r}\geq 1\) for \(i=1,\ldots,m\). This implies that \(\{z_1,\ldots,z_r\}\cap S_i\neq\emptyset\) for each \(i=1,\ldots,m\), and so \(\{x_{z_1},\ldots,x_{z_r}\}\cap \mathfrak{p}_i\neq\emptyset\) for all \(i=1,\ldots,m\). We can deduce that \(x_{z_1}\cdots x_{z_r}\in\mathfrak{p}_i\) for all \(i=1,\ldots,m\), and hence \(x_{z_1}\cdots x_{z_r}\in \cap_{i=1}^m\mathfrak{p}_i\). As \(NI(G)=\cap_{i=1}^m\mathfrak{p}_i\) and \(NI(G)=(x_{\theta_{t,1}}\cdots x_{\theta_{t,r}}:t=1,\ldots,n)\), we get there exists an element \(x_{\theta_{s,1}}\cdots x_{\theta_{s,r}}\in G(NI(G))\) for some \(1\leq s\leq n\) such that \(x_{\theta_{s,1}}\cdots x_{\theta_{s,r}}=x_{z_1}\cdots x_{z_r}\), and therefore \(\{z_1,\ldots,z_r\}=\Gamma_s\), as required.

Moreover, since G is an (r-1)-regular graph, we derive there exist r sets \(N_G[i_1], \ldots, N_G[i_r]\) with \(t \in N_G[i_k]\) for all \(k = 1, \ldots, r\). Since G is undirected, this is equivalent to this statement that \(\theta_{t,i} \in N_G[t]\) if and only if \(t \in N_G[\theta_{t,i}]\) for \(i = 1, \ldots, r\) and \(t = 1, \ldots, n\). This yields that \(M(\mathcal{S})\) satisfies Condition (iv).

Conversely, assume that the matrix \(M(\mathcal{S})\) satisfies Conditions (i)-(iv). Our aim is to verify the existence of an (r-1)-regular graph G with V(G)=V where \(\mathcal{S}\) is the set whose elements are the minimal dominating sets of G. Condition (iv) gives that there exist n subsets \(\Gamma_t=\{\theta_{t,1},\ldots,\theta_{t,r}\}\subseteq\{1,\ldots,n\}\) for any integer \(1\leq t\leq n\) such that \(a_{i,\theta_{t,1}}+\cdots+a_{i,\theta_{t,r}}\geq 1\) for \(i=1,\ldots,m\) and \(t=1,\ldots,n\), and also for any integer \(1\leq t\leq n\) there exist r sets \(\Gamma_{i_1},\ldots,\Gamma_{i_r}\) with \(t\in\Gamma_{i_k}\) for all \(k=1,\ldots,r,\) \(t\in\Gamma_t\), and \(\theta_{t,i}\in\Gamma_t\) if and only if \(t\in\Gamma_{\theta_{t,i}}\) for all \(i=1,\ldots,r\). Hence, we define an (r-1)-regular graph G with \(N_G[t]:=\Gamma_t=\{\theta_{t,1},\ldots,\theta_{t,r}\}\) for any integer \(1\leq t\leq n\). In other words, Conditions (iv)(a)-(d) guarantee the existence of such a graph G. In particular, one can conclude from the definition of closed neighborhood ideal of G that \(NI(G)=(x_{\theta_{t,1}}\cdots x_{\theta_{t,r}}:\ t=1,\ldots,n)\).

In what follows, we prove that every element of S is a minimal dominating set of G. To see this, we first show that \(S_1, \ldots, S_m\) are dominating sets of G. To do this, assume that \(N_G[t] = \{\theta_{t,1}, \ldots, \theta_{t,r}\}\) is the closed neighborhood of the vertex t with \(1 \le t \le n\). By Condition (iv)(a), we have that \(a_{i,\theta_{t,1}} + \cdots + a_{i,\theta_{t,r}} \ge 1\) for all \(i = 1, \ldots, m\). Since, for all \(i = 1, \ldots, m\), the i-th row of the matrix M(S) is associated to \(S_i\) and \(a_{i,\theta_{t,1}} + \cdots + a_{i,\theta_{t,r}} \ge 1\), we obtain \(\{\theta_{t,1}, \ldots, \theta_{t,r}\} \cap S_i \ne \emptyset\) for all \(i = 1, \ldots, m\). Consequently, \(N_G[t] \cap S_i \ne \emptyset\), and so \(S_i\) is a dominating set of G for all \(i = 1, \ldots, m\).

Here, we claim that if D is an arbitrary dominating set of G, then \(S_i \subseteq D\) for some \(1 \le i \le m\). On the contrary, assume that \(S_i \nsubseteq D\) for each \(i = 1, \ldots, m\). Thus there exists an element \(f_i \in S_i \setminus D\) for all \(i = 1, \ldots, m\). Suppose that \(\bigcup_{i=1}^m \{f_i\} = \{y_1, \ldots, y_{\lambda}\}\) such that \(y_1 < \cdots < y_{\lambda}\) are \(\lambda\) distinct integers. Because \(\bigcup_{i=1}^m \{f_i\} = \{y_1, \ldots, y_{\lambda}\}\), we get \(f_i \in \{y_1, \ldots, y_{\lambda}\}\) for all \(i = 1, \ldots, m\).

Thus, we deduce that there exists a positive integer \(k_i\) with \(1 \leq k_i \leq \lambda\) such that \(f_i = y_{k_i}\) for all \(i = 1, \ldots, m\). Due to \(f_i \in S_i\) for all \(i = 1, \ldots, m\), this implies that \(y_{k_i} \in S_i\) for all \(i = 1, \ldots, m\). Since, for all \(i = 1, \ldots, m\), the i-th row of the matrix \(M(\mathcal{S})\) is associated to \(S_i, y_{k_i} \in S_i\), and \(1 \leq k_i \leq \lambda\), this yields that \(a_{i,y_1} + \cdots + a_{i,y_{\lambda}} \geq 1\) for each \(i = 1, \ldots, m\). We prove that \(\lambda \geq r\). Suppose, on the contrary, that \(\lambda \leq r - 1\). If \(\lambda = r - 1\), then \(a_{i,y_1} + \cdots + a_{i,y_{r-1}} \geq 1\) for each \(i = 1, \ldots, m\), which is a contradiction with Condition (ii). Now, let \(\lambda < r - 1\), then this gives that one can choose \(r - 1 - \lambda\) distinct integers \(z_1, \ldots, z_{r-1-\lambda} \in \{1, \ldots, n\} \setminus \{y_1, \ldots, y_{\lambda}\}\). On account of \(a_{i,y_1} + \cdots + a_{i,y_{\lambda}} \geq 1\) for each \(i = 1, \ldots, m\), one obtains \(a_{i,y_1} + \cdots + a_{i,y_{\lambda}} + a_{i,z_1} + \cdots + a_{i,z_{r-1-\lambda}} \geq 1\) for each \(i = 1, \ldots, m\). This contradicts Condition (ii), and hence we derive \(\lambda \geq r\). It follows from Condition (iii) that there exist at least r distinct integers \(y_{\alpha_1}, \ldots, y_{\alpha_r} \in \{y_1, \ldots, y_{\lambda}\}\) such that \(a_{i,y_{\alpha_1}} + \cdots + a_{i,y_{\alpha_r}} \geq 1\) for all \(i = 1, \ldots, m\). In view of Condition (iv)(a), this implies that \(\{y_{\alpha_1}, \ldots, y_{\alpha_r}\} = \Gamma_s = N_G[s]\) for some \(1 \leq s \leq n\). Thus, \(\{y_{\alpha_1}, \ldots, y_{\alpha_r}\} \cap D \neq \emptyset\), and so \(\{y_1, \ldots, y_{\lambda}\} \cap D \neq \emptyset\). This yields that \((\bigcup_{i=1}^m \{f_i\}) \cap D \neq \emptyset\), which is a contradiction. Hence, one can conclude that if D is an arbitrary dominating set of G, then \(S_i \subseteq D\) for some \(1 \leq i \leq m\). On the other hand, Condition (i) gives that \(S_i \nsubseteq S_j\) for each \(1 \leq i, j \leq m\) with \(i \neq j\). Consequently, we derive that \(S_1, \ldots, S_m\) are the minimal dominating sets of G, and so the proof is over.

The next example illustrates how we can employ Theorem 3.1.

Example 3.1. Assume that \(V = \{x_1, \dots, x_6\}\) and the \(S_i\)'s are a non-empty set of V as follows:

\[S_{1} = \{x_{1}, x_{2}\}, S_{2} = \{x_{1}, x_{4}\}, S_{3} = \{x_{1}, x_{6}\}, S_{4} = \{x_{2}, x_{3}\}, S_{5} = \{x_{2}, x_{5}\},\] \[S_{6} = \{x_{3}, x_{4}\}, S_{7} = \{x_{3}, x_{6}\}, S_{8} = \{x_{4}, x_{5}\}, S_{9} = \{x_{5}, x_{6}\}, S_{10} = \{x_{1}, x_{3}, x_{5}\},\] \[S_{11} = \{x_{2}, x_{4}, x_{6}\}.\]

Conditions (ii) and (iii) force us to seek a 3-regular graph G. It is not hard to observe that the matrix M(S) associated to S is the following matrix:

\[M(\mathcal{S}) = \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \end{pmatrix}.\]

It is easy to investigate that Condition (i) holds. In order to show Condition (ii), we should check that for each r-1=3 distinct integers \(1 \le j_1, j_2, j_3 \le 6\), there exists a positive integer \(1 \le i \le 11\) such that \(a_{i,j_1} + a_{i,j_2} + a_{i,j_3} = 0\). To do this, we have to examine it \(\binom{6}{3} = 20\) times. This proves that \(M(\mathcal{S})\) satisfies Condition (ii). Moreover, for verifying Condition (iii), one must check

that for each \(4 \le \ell \le 6\) and distinct integers \(1 \le j_1, \ldots, j_\ell \le 6\) such that \(a_{i,j_1} + \cdots + a_{i,j_\ell} \ge 1\) for all \(i = 1, \ldots, 11\), then there exist at least four distinct integers \(j_{\alpha_1}, j_{\alpha_2}, j_{\alpha_3}, j_{\alpha_4} \in \{j_1, \ldots, j_\ell\}\) such that \(a_{i,j_{\alpha_1}} + a_{i,j_{\alpha_2}} + a_{i,j_{\alpha_3}} + a_{i,j_{\alpha_4}} \ge 1\) for all \(i = 1, \ldots, 11\). Hence, we have to check Condition (iii) exactly \(\binom{6}{4} + \binom{6}{5} + \binom{6}{6} = 22\) times. After checking them, we derive that Condition (iii) holds. Finally, direct computations show that after checking \(\binom{6}{4} = 15\) cases, there exist exactly six subsets \(\Gamma_1 := \{1, 2, 4, 6\}, \Gamma_2 := \{1, 2, 3, 5\}, \Gamma_3 := \{2, 3, 4, 6\}, \Gamma_4 := \{1, 3, 4, 5\}, \Gamma_5 := \{2, 4, 5, 6\},\) and \(\Gamma_6 := \{1, 3, 5, 6\}\) which satisfy Condition (iv).

Since Conditions (i)-(iv) hold, according to Theorem 3.1, one can deduce that the closed neighborhood ideal of G is given by

\[NI(G) = (x_1x_2x_4x_6, x_1x_2x_3x_5, x_2x_3x_4x_6, x_1x_3x_4x_5, x_2x_4x_5x_6, x_1x_3x_5x_6).\]

Since \(x_1x_2x_4x_6 \in NI(G)\), one may consider the following cases:

Case 1. \(N_G(1) = \{2,4,6\}\). Because \(x_1x_2x_3x_5 \in NI(G)\), one can conclude that \(N_G(2) = \{1,3,5\}\). Furthermore, thanks to \(N_G(2) = \{1,3,5\}\) and \(x_2x_3x_4x_6 \in NI(G)\), this implies that \(N_G(3) = \{2,4,6\}\). Due to \(N_G(3) = \{2,4,6\}\) and \(x_1x_3x_4x_5 \in NI(G)\), we get \(N_G(4) = \{1,3,5\}\). It follows from \(N_G(4) = \{1,3,5\}\) and \(x_2x_4x_5x_6 \in NI(G)\) that \(N_G(5) = \{2,4,6\}\). Finally, since \(N_G(5) = \{2,4,6\}\) and \(x_1x_3x_5x_6 \in NI(G)\), this gives that \(N_G(6) = \{1,3,5\}\). Therefore, we deduce that G is the graph \(G_1\) which has been shown in the figure below.

Case 2. \(N_G(2) = \{1, 4, 6\}\) and \(N_G(4) = \{2, 3, 6\}\). A similar argument yields that \(N_G(1) = \{2, 3, 5\}\), \(N_G(3) = \{1, 4, 5\}\), \(N_G(5) = \{1, 3, 6\}\), and \(N_G(6) = \{2, 4, 5\}\). We thus gain that G is isomorphic to \(G_2\) which has been shown in the figure below.

Case 3. \(N_G(2) = \{1, 4, 6\}\) and \(N_G(6) = \{2, 3, 4\}\). Following a similar discussion, we get \(N_G(1) = \{2, 3, 5\}\), \(N_G(3) = \{1, 5, 6\}\), \(N_G(4) = \{2, 5, 6\}\), and \(N_G(5) = \{1, 3, 4\}\). Consequently, one has G is isomorphic to \(G_2\).

Case 4. \(N_G(4) = \{1, 2, 6\}\) and \(N_G(3) = \{1, 2, 5\}\). A similar discussion gives rise to \(N_G(1) = \{3, 4, 5\}\), \(N_G(2) = \{3, 4, 6\}\), \(N_G(5) = \{1, 3, 6\}\), and \(N_G(6) = \{2, 4, 5\}\). One can easily check that G is isomorphic to \(G_2\).

Figure 1. Graphs \(G_1\) and \(G_2\).

• Case 5. NG(4) = {1, 2, 6} and NG(5) = {1, 2, 3}. A similar argument implies that NG(1) = {3, 4, 5}, NG(2) = {4, 5, 6}, NG(3) = {1, 5, 6}, and NG(6) = {2, 3, 4}. It is not hard to investigate that G is isomorphic to G2.
• Case 6. NG(6) = {1, 2, 4} and NG(5) = {1, 2, 3}. By a similar discussion, we obtain that NG(1) = {3, 5, 6}, NG(2) = {4, 5, 6}, NG(3) = {1, 4, 5}, and NG(4) = {2, 3, 6}. One can rapidly check that G is isomorphic to G2.
• Case 7. NG(6) = {1, 2, 4} and NG(3) = {1, 2, 5}. A similar argument yields that NG(1) = {3, 5, 6}, NG(2) = {3, 4, 6}, NG(4) = {2, 5, 6}, and NG(5) = {1, 3, 4}. We can easily see that G is isomorphic to G2.
• Since G¹ has no induced odd cycle, this implies that G¹ is bipartite, while G² has an induced odd cycle, and so is non-bipartite. This yields that G¹ and G² are non-isomorphic.

Acknowledgment

The author is deeply grateful to the anonymous referee for her/his careful reading of the manuscript and for her/his valuable, detailed and informative suggestions and comments on this manuscript. Part of this work was carried out while Mehrdad Nasernejad, in 2021, was invited CNRS Researcher at the Fed´ eration de Recherche Math ´ ematique des Hauts-de-France (FR2037 ´ CNRS), working at the Laboratoire de Mathematiques de Lens of the Universit ´ e d'Artois (France). ´

References

• [1] J.A. Bondy and U.S.R. Murty, Graph Theory. Graduate Texts in Mathematics, 244. Springer, New York, 2008.
• [2] J. Herzog and T. Hibi, Monomial Ideals. Graduate Texts in Mathematics 260 Springer-Verlag, 2011.
• [3] J. Honeycutt and S.K. Sather-Wagstaff, Closed neighborhood ideals of finite simple graphs, La Matematica 1 (2022), 387–394.
• [4] J. Mart´ı-Farre, Sets defining minimal vertex covers, ´ Discrete Math. 197/198 (1999), 555– 559.
• [5] D.A. Mojdeh M. Alishahi, Outer independent global dominating set of trees and unicyclic graphs, Electron. J. Graph Theory Appl. 7 (1) (2019), 121–145.
• [6] D.A. Mojdeh, S.R. Musawi, and E. Nazari Kiashi, On the distance domination number of bipartite graphs, Electron. J. Graph Theory Appl. 8 (2) (2020), 353–364.
• [7] M. Nasernejad, S. Bandari, and L.G. Roberts, Normality and associated primes of closed neighborhood ideals and dominating ideals, J. Algebra Appl., 2023, doi:10.1142/S0219498825500094.

• [8] M. Nasernejad and K. Khashyarmanesh, Sets defining minimal vertex covers of uniform hypergraphs, Ars Combin. 147 (2019), 135–142.
• [9] M. Nasernejad, A.A. Qureshi, S. Bandari, and A. Musapas¸aoglu, Dominating ideals and ˘ closed neighborhood ideals of graphs, Mediterranean Journal of Mathematics, 19, Article number: 152 (2022).
• [10] L. Sharifan and S. Moradi, Closed neighborhood ideal of a graph, Rocky Mountain J. Math. 50 (3) (2020), 1097–1107.
• [11] R.H. Villarreal, Cohen–Macaulay graphs, Manuscripta Math. 66 (1990), 277–293.
• [12] R.H. Villarreal, Monomial Algebras. 2nd. Edition, Monographs and Research Notes in Mathematics, CRC Press, Boca Raton, FL, 2015.
• [13] D.B. West, Introduction to graph theory. Prentice Hall, Inc., Upper Saddle River, NJ, 1996. xvi+512 pp. ISBN: 0-13-227828-6.