# Graphs Associated with the Ideals of a Numerical Semigroup Having Metric Dimension 2

Authors: Ying Wang; Muhammad Ahsan Binyamin; Wajid Ali; Adnan Aslam; Yongsheng Rao
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

LetΛ be a numerical semigroup and I⊂Λ be an irreducible ideal of Λ. The graph GIΛ assigned to an ideal I of Λ is a graph with elements of Λ∖I∗ as vertices, and any two vertices xandy are adjacent if and only if x+y∈I. In this work, we give a complete characterization (up to isomorphism) of the graph GIΛ having metric dimension 2.


---

## Body

## 1. Introduction

In algebraic combinatorics, the study of graphs associated with algebraic objects is one of the most important and fascinating fields of research. During the last couple of decades, a lot of research is carried out in this field. There are many papers on assigning graphs to rings, groups, and semigroups [1–6]. Several authors [7–13] studied different properties of these graphs including diameter, girth, domination, metric dimension, central sets, and planarity.We start by defining some basic concept related to graph theory. A graphG=VG,EG has a vertex set VG and the edge set EG. The cardinality of the vertex set and edge set is called the order and size of G, respectively. A path in G is a sequence of edges u1u2,u2u3,…,uk−1uk. A graph G is connected if every pair of vertices x,y∈VG is connected by a path. The distance between two vertices x,y∈VG is denoted by dx,y and is the length of the shortest path between them. The diameter of G is denoted by dG and is defined as the largest distance between the vertices of G. Let U=u1,u2,…,ur be an ordered subset of VG. Then, the r−tuple du,u1,du,u2,…,du,ur is the representation u with respect to U. The vertex u is said to be resolved by U if du,u1,du,u2,…,du,ur≠dv,u1,dv,u2,…,dv,ur for any vertex v∈VG. The set U is called resolving set of G if distinct vertices of G have distinct representations with respect to U, and it is called basis of G if it is a resolving set with minimal cardinality. The metric dimension of G, denoted by μG, is the cardinality of basis. The concept of metric dimension was introduced by Slater [14] and later studied by Harary and Melter [15]. It has many applications, for example, robot navigation [16], pharmaceutical chemistry [17, 18], sonar and coast guard long range navigation [14], and combinatorial optimization [19].Letℕ be set of nonnegative integers. A subset Λ⊂ℕ is said to be numerical semigroup if the following holds:(1)
0∈Λ(2)
x+y∈Λ for all x,y∈Λ(3)
ℕ∖Λ is finiteIt is easy to observe that the numerical semigroup is a commutative monoid. Thus, the set of numerical semigroups classifies the set of all submonoids ofℕ,+. The elements of the set ℕ∖Λ are called gaps of Λ, and the largest element of this set is known as Frobenius number. Note that every numerical semigroup is finitely generated; that is, there exist a set A=a1,a2,…,at such that Λ=A=n1a1+…ntat:n1,…nt∈ℕ. Moreover, every numerical semigroup has a unique minimal system of generators. The cardinality of the minimal system of generators is called embedding dimension of Λ. It is denoted by eΛ. A subset I of numerical semigroup Λ is ideal (integral ideal) of Λ if for all x∈I and s∈Λ and the element x+s∈I. An ideal I is called irreducibly ideal if it cannot be written as intersections of two or more than two ideals which contained it properly. For more details on theory of numerical semigroup, the interested readers can refer to [20].Recently, several authors studied the metric dimension of the graphs associated with the algebraic objects. Soleymanivarniab et al. [21] gave some metric dimension formula for annihilator graphs. Bailey et al. [22] studied the constructions of resolving sets of Kneser and Johnson graphs and provided bounds on their metric dimension. Faisal et al. [23] studied the metric dimension of the commuting graph of a dihedral group. The metric dimension of a zero-divisor graph of a commutative ring was studied in [13], while the metric dimension of a total graph of a finite commutative ring was studied in [24]. For more results on the metric dimension, we refer the readers to [25–30].


## 2. Notation and Preliminaries

LetΛ=A be a numerical semigroup, where A=a1,a2,…,an is the minimal system of generators of Λ. Then, every x∈Λ has a representation of the form u1a1+u2a2+⋯+unan, where u1,u2,…,un are nonnegative integers. Let 1≤p≤n be a fixed integer. We say that an element x∈Λ has a p-representation if there exist ai1,ai2,…,aip∈A and ui1,ui2,…,uip positive integers such that x=ui1ai1+ui2ai2+⋯+uipaip; that is, x can be written as linear combination of exactly p generator of Λ. Let Λp denote the set containing all the elements x∈Λ, which have a p representation. It is easy to see that(1)Λ=∪p=1nΛp.Note that an elementx∈Λ may have more than one p representations. For an element x∈Λp, we use the notation Σp if it has a unique p representation and Σp,1,Σp,2,…,Σp,r if it has r number of p representations. Let Σp∈Λp, then there exist two p-tuples, the coefficients p tuple ui1,ui2,…,uip∈ℤ>0p, and the generators p-tuple ai1,ai2,…,aip∈ℤ>0p such that Σp=ui1ai1+ui2ai2+⋯+uipaip. We denote the coefficient and generators p tuple of an element Σp by cΣp and gΣp, respectively. Also, the j-th component of cΣp and gΣp is denoted by cjΣp and gjΣp, respectively. By using the above notations, for any x∈Λ, we define(2)Λpx=Σp:Σp=x,Λx=∪p=1nΛpx.For ap-representation Σp=ui1ai1+ui2ai2+⋯+uipaip, we set(3)BΣp=vi1ai1+vi2ai2+⋯+vipaip:0≤vij≤uij,1≤j≤p.Lemma 1.
With the notations defined above, we have(4)ℬx=∪Σp∈ΛxℬΣp.Proof.
The proof of this lemma follows from the definition ofℬx.
LetΛ be a numerical semigroup and I⊂Λ be irreducible ideal of Λ. Binyamin et al. [31] assigned a graph to numerical semigroup Λ and studied its properties. Peng Xu et al. [32] assign a graph GIΛ to the ideal I of numerical semigroup Λ with vertex set VGIΛ=Λ∖I∗ and two vertices x,y are adjacent if and only if x+y∈I. Barucci [33] showed that every irreducible ideal I of numerical semigroup Λ can be expressed in the form Λ∖Bx, where Bx=y∈Λ:x−y∈Λ, for some x∈Λ. Hence, the vertex set of the graph GIΛ is the set vi:i∈B∗x for some x∈Λ. Peng Xu et al. [32] proved that the graph GIΛ is always connected and diameter 2. The aim of this paper is to find all the graphs GIΛ having metric dimension 2. The following result by Chartrand et al. [18] gives bound on the order of graph with given metric dimension k and diameter d.Theorem 1.
LetG be a graph with metric dimension k and VG=n. Let d be the diameter of G. Then, VG≤dk+k.Hence, to find graphsGIΛ with metric dimension 2, it is enough to classify all graphs GIΛ of order less than or equal to 6. In the next section, we give bounds for the graphs GIΛ of orders 4 and 5.


### 2.1. Bounds for the GraphsGIΛ of Orders 4 and 5

Lemma 2.
LetΛ=A be a numerical semigroup of embedding dimension n≥2. Then, GIΛ≠4, if one of the following holds:(1)
Λpx≠∅ for some p≥3.(2)
Λ1x≥3.(3)
Λ2x≥2.(4)
Λ1x=∅ and Λ2x=1.(5)
Λ1x=2 and Λ2x=1.Proof.
(1)
IfΛpx≠∅ for some p≥3, then there is a p-representation Σp of x in Λpx. This gives g1Σp,g2Σp,g3Σp,g1Σp+g2Σp,g1Σp+g3Σp,g2Σp+g3Σp,x∈ℬ∗Σp⊆ℬ∗x. This implies GIΛ≠4.(2)
IfΛ1x≥3, then there are Σ1,1,Σ1,2,…,Σ1,r∈Λ1x with r≥3. We assume that gΣ1,1<gΣ1,2<⋯<gΣ1,r and then cΣ1,1≥5. This gives gΣ1,1,2gΣ1,1,3gΣ1,1,4gΣ1,1,5gΣ1,1∈ℬ∗Σ1,1, and therefore, GIΛ≠4.(3)
IfΛ2x≥2, then we have Σ2,1,Σ2,2,…,Σ2,s∈Λ2x with s≥2. One can easily see that ℬ∗Σ2,1∪ℬ∗Σ2,2∪…∪ℬ∗Σ2,s must contain g1Σ2,1, g2Σ2,1, g1Σ2,2, g2Σ2,2, g1Σ2,1+g2Σ2,1 and g1Σ2,2+g2Σ2,2. Therefore, GIΛ≠4.(4)
Lemma 1: IfΛ1x=∅ and Λ2x=1 then there is the unique 2-representation Σ2 of x. Now if Λpx≠∅ for some p≥3 then from (1), it follows that GIΛ≠4, and if Λpx=∅ for all p≥3, then gives ℬ∗x=ℬ∗Σ2. So if cΣ2=1,1, then GIΛ=3; otherwise, GIΛ>4. Consequently, GIΛ≠4.(5)
IfΛ1x=2 and Λ2x=1, then we can assume Σ1,1,Σ1,2∈Λ1x and Σ2∈Λ2x. This gives gΣ1,1,gΣ1,2,g1Σ2,g2Σ2,g1Σ2+g2Σ2 are in ℬ∗x, and therefore, GIΛ≠4.Lemma 3.
LetΛ=A be a numerical semigroup of embedding dimension n≥2. Then, GIΛ≠5, if one of the following holds:(1)
Λpx≠∅ for some p≥3.(2)
Λ1x≥2.(3)
Λ2x≥3.(4)
Λ1x=1 and Λ2x=2.Proof.
This lemma can be proved in a similar way as we proved Lemma2.


### 2.2. Computation of Irreducible Ideals for the GraphsGIΛ of Orders 4 and 5

Lemma 4.
LetΛ=A be a numerical semigroup of embedding dimension n≥2. If GIΛ=4, then x is one of the following:(1)
x=4gΣ1.(2)
x=3gΣ1,1 and x=2gΣ1,2.(3)
x=2gΣ1 and x=g1Σ2+g2Σ2.Proof.
IfGIΛ=4, then from Lemma 2, it follows that x∈Λ satisfies one of the following conditions:Λ1x≤2 and Λpx=∅, ∀p≥2.Λ1x=1, Λ2x=1 and Λpx=∅, ∀p≥3.
IfΛ1x=1 and Λpx=∅, ∀p≥2, then x has a unique 1-representation Σ1. By Lemma 1, we get ℬ∗x=ℬ∗Σ1=gΣ1,2gΣ1,…,cΣ1.gΣ1. As ∣GIΛ∣=4, it follows that cΣ1=4. This gives case (1).
Now ifΛ1x=2 and Λpx=∅, ∀p≥2, then there are exactly two 1-representations, say Σ1,1 and Σ1,2 of x. Assume that gΣ1,1<gΣ1,2, then cΣ1,2<cΣ1,1 and cΣ1,1 is not a multiple of cΣ1,2. Then, it follows from Lemma 1 that(5)ℬ∗x=ℬ∗Σ1,1∪ℬ∗Σ1,2=gΣ1,1,2gΣ1,1,…,cΣ1,1.gΣ1,1∪gΣ1,2,2gΣ1,2…,cΣ1,2.gΣ1,2=gΣ1,1,2gΣ1,1,…,cΣ1,1.gΣ1,1,gΣ1,2,2gΣ1,2,…,cΣ1,2.gΣ1,2.
We show thatℬ∗Σ1,1∩ℬ∗Σ1,2∖cΣ1,2.gΣ1,2=∅. Let p.gΣ1,1=q.gΣ1,2 for some q<p<cΣ1,1 with q=2,3,…,cΣ1,2−1. Then, p.gΣ1,1+cΣ1,1−p.gΣ1,1=cΣ1,1.gΣ1,1, and we get q.gΣ1,2+cΣ1,1−p.gΣ1,1=x. This gives Λ2x≠∅, a contradiction. Therefore, we have ℬ∗x=cΣ1,1+cΣ1,2−1. As GIΛ=4, cΣ1,1=3 and gΣ1,2=2 is the only possibility. This gives case (2).
LetΛ1x=1=Λ2x and Λpx=∅, ∀p≥3. Then, we can assume Σ1∈Λ1x and Σ2∈Λ2x are the only possible 1-representation and 2-representation of x, respectively. By (2) in Lemma 2, we have cΣ2=1,1. In this case, it is easy to see that ℬ∗x=gΣ1,2gΣ1,…,cΣ1.gΣ1,g1Σ2,g2Σ2. Then, ℬ∗x=4 gives cΣ1=2 and we get case (3).Lemma 5.
LetΛ=A be a numerical semigroup of embedding dimension n≥2. If GIΛ=5, then x is one of the following:(1)
x=5gΣ1.(2)
x=2g1Σ2+g2Σ2.(3)
x=g1Σ2,1+g2Σ2,1 and x=g1Σ2,2+g2Σ2,2.(4)
x=3gΣ1 and x=g1Σ2+g2Σ2.Proof.
Given thatGIΛ=5, then from Lemma 5, it follows that x∈Λ satisfies one of the following conditions:Λ1x=1 and Λpx=∅, ∀p≥2.Λ2x≤2 and Λpx=∅, ∀p≠2.Λ1x=1, Λ2x=1 and Λpx=∅, ∀p≥3.
These possibilities can be checked in a similar way as we did in Lemma4 to get the required result.


## 2.1. Bounds for the GraphsGIΛ of Orders 4 and 5

Lemma 2.
LetΛ=A be a numerical semigroup of embedding dimension n≥2. Then, GIΛ≠4, if one of the following holds:(1)
Λpx≠∅ for some p≥3.(2)
Λ1x≥3.(3)
Λ2x≥2.(4)
Λ1x=∅ and Λ2x=1.(5)
Λ1x=2 and Λ2x=1.Proof.
(1)
IfΛpx≠∅ for some p≥3, then there is a p-representation Σp of x in Λpx. This gives g1Σp,g2Σp,g3Σp,g1Σp+g2Σp,g1Σp+g3Σp,g2Σp+g3Σp,x∈ℬ∗Σp⊆ℬ∗x. This implies GIΛ≠4.(2)
IfΛ1x≥3, then there are Σ1,1,Σ1,2,…,Σ1,r∈Λ1x with r≥3. We assume that gΣ1,1<gΣ1,2<⋯<gΣ1,r and then cΣ1,1≥5. This gives gΣ1,1,2gΣ1,1,3gΣ1,1,4gΣ1,1,5gΣ1,1∈ℬ∗Σ1,1, and therefore, GIΛ≠4.(3)
IfΛ2x≥2, then we have Σ2,1,Σ2,2,…,Σ2,s∈Λ2x with s≥2. One can easily see that ℬ∗Σ2,1∪ℬ∗Σ2,2∪…∪ℬ∗Σ2,s must contain g1Σ2,1, g2Σ2,1, g1Σ2,2, g2Σ2,2, g1Σ2,1+g2Σ2,1 and g1Σ2,2+g2Σ2,2. Therefore, GIΛ≠4.(4)
Lemma 1: IfΛ1x=∅ and Λ2x=1 then there is the unique 2-representation Σ2 of x. Now if Λpx≠∅ for some p≥3 then from (1), it follows that GIΛ≠4, and if Λpx=∅ for all p≥3, then gives ℬ∗x=ℬ∗Σ2. So if cΣ2=1,1, then GIΛ=3; otherwise, GIΛ>4. Consequently, GIΛ≠4.(5)
IfΛ1x=2 and Λ2x=1, then we can assume Σ1,1,Σ1,2∈Λ1x and Σ2∈Λ2x. This gives gΣ1,1,gΣ1,2,g1Σ2,g2Σ2,g1Σ2+g2Σ2 are in ℬ∗x, and therefore, GIΛ≠4.Lemma 3.
LetΛ=A be a numerical semigroup of embedding dimension n≥2. Then, GIΛ≠5, if one of the following holds:(1)
Λpx≠∅ for some p≥3.(2)
Λ1x≥2.(3)
Λ2x≥3.(4)
Λ1x=1 and Λ2x=2.Proof.
This lemma can be proved in a similar way as we proved Lemma2.


## 2.2. Computation of Irreducible Ideals for the GraphsGIΛ of Orders 4 and 5

Lemma 4.
LetΛ=A be a numerical semigroup of embedding dimension n≥2. If GIΛ=4, then x is one of the following:(1)
x=4gΣ1.(2)
x=3gΣ1,1 and x=2gΣ1,2.(3)
x=2gΣ1 and x=g1Σ2+g2Σ2.Proof.
IfGIΛ=4, then from Lemma 2, it follows that x∈Λ satisfies one of the following conditions:Λ1x≤2 and Λpx=∅, ∀p≥2.Λ1x=1, Λ2x=1 and Λpx=∅, ∀p≥3.
IfΛ1x=1 and Λpx=∅, ∀p≥2, then x has a unique 1-representation Σ1. By Lemma 1, we get ℬ∗x=ℬ∗Σ1=gΣ1,2gΣ1,…,cΣ1.gΣ1. As ∣GIΛ∣=4, it follows that cΣ1=4. This gives case (1).
Now ifΛ1x=2 and Λpx=∅, ∀p≥2, then there are exactly two 1-representations, say Σ1,1 and Σ1,2 of x. Assume that gΣ1,1<gΣ1,2, then cΣ1,2<cΣ1,1 and cΣ1,1 is not a multiple of cΣ1,2. Then, it follows from Lemma 1 that(5)ℬ∗x=ℬ∗Σ1,1∪ℬ∗Σ1,2=gΣ1,1,2gΣ1,1,…,cΣ1,1.gΣ1,1∪gΣ1,2,2gΣ1,2…,cΣ1,2.gΣ1,2=gΣ1,1,2gΣ1,1,…,cΣ1,1.gΣ1,1,gΣ1,2,2gΣ1,2,…,cΣ1,2.gΣ1,2.
We show thatℬ∗Σ1,1∩ℬ∗Σ1,2∖cΣ1,2.gΣ1,2=∅. Let p.gΣ1,1=q.gΣ1,2 for some q<p<cΣ1,1 with q=2,3,…,cΣ1,2−1. Then, p.gΣ1,1+cΣ1,1−p.gΣ1,1=cΣ1,1.gΣ1,1, and we get q.gΣ1,2+cΣ1,1−p.gΣ1,1=x. This gives Λ2x≠∅, a contradiction. Therefore, we have ℬ∗x=cΣ1,1+cΣ1,2−1. As GIΛ=4, cΣ1,1=3 and gΣ1,2=2 is the only possibility. This gives case (2).
LetΛ1x=1=Λ2x and Λpx=∅, ∀p≥3. Then, we can assume Σ1∈Λ1x and Σ2∈Λ2x are the only possible 1-representation and 2-representation of x, respectively. By (2) in Lemma 2, we have cΣ2=1,1. In this case, it is easy to see that ℬ∗x=gΣ1,2gΣ1,…,cΣ1.gΣ1,g1Σ2,g2Σ2. Then, ℬ∗x=4 gives cΣ1=2 and we get case (3).Lemma 5.
LetΛ=A be a numerical semigroup of embedding dimension n≥2. If GIΛ=5, then x is one of the following:(1)
x=5gΣ1.(2)
x=2g1Σ2+g2Σ2.(3)
x=g1Σ2,1+g2Σ2,1 and x=g1Σ2,2+g2Σ2,2.(4)
x=3gΣ1 and x=g1Σ2+g2Σ2.Proof.
Given thatGIΛ=5, then from Lemma 5, it follows that x∈Λ satisfies one of the following conditions:Λ1x=1 and Λpx=∅, ∀p≥2.Λ2x≤2 and Λpx=∅, ∀p≠2.Λ1x=1, Λ2x=1 and Λpx=∅, ∀p≥3.
These possibilities can be checked in a similar way as we did in Lemma4 to get the required result.


## 3. GraphsGIΛ with Metric Dimension 2

Theorem 2.
There are exactly 5 nonisomorphic graphsGIΛ with metric dimension 2.We prove Theorem2 in a sequence of following lemmas.Lemma 6.
There are exactly 2 nonisomorphic graphsGIΛ with 4 or less vertices and metric dimension 2.Proof.
It is trivial to note that no such graph exists forGIΛ=2,3.
Now ifGIΛ=4, then from Lemma 4, we have the following possibilities:(1)
x=4gΣ1 with Λpx=∅, ∀p≥2.(2)
x=3gΣ1,1=2gΣ1,2 with Λpx=∅, ∀p≥2.(3)
x=2gΣ1=g1Σ2+g2Σ2 with Λpx=∅, ∀p≥3.
If (1) holds, then I=Λ∖ℬ∗4gΣ1, and therefore, GIΛ is isomorphic to the graph given in Figure 1. So metric dimension of GIΛ is 2.
Now if (2) or (3) holds, then either I=Λ∖ℬ∗3gΣ1,1 or I=Λ∖ℬ∗2gΣ1. In both cases, GIΛ is isomorphic to the graph given in Figure 2, and therefore, metric dimension of GIΛ is 2.Figure 1
GraphsGIΛ When x=4gΣ1 with Λpx=0, ∀p≥2.Figure 2
GraphGIΛ for the remaining two cases.Lemma 7.
There are exactly 3 nonisomorphic graphsGIΛ with 5 vertices and metric dimension 2.Proof.
IfGIΛ=5, then from Lemma 5, we have the following possibilities:(1)
x=5gΣ1 with Λpx=∅, ∀p≥2.(2)
x=2g1Σ2+g2Σ2 with Λpx=∅, ∀p≠2.(3)
x=g1Σ2,1+g2Σ2,1=g1Σ2,2+g2Σ2,2 with Λpx=∅, ∀p≠2.(4)
x=3gΣ1 and x=g1Σ2+g2Σ2 with Λpx=∅, ∀p≥3.
If (1) holds, then I=Λ∖ℬ∗5gΣ1, and therefore, GIΛ is isomorphic to the graph given in Figure 3.
Now, if (2) holds, then I=Λ∖ℬ∗2g1Σ2+g2Σ2, and therefore, GIΛ is isomorphic to the graph given in Figure 4.
If (3) or (4) holds, then I=Λ∖ℬ∗g1Σ2,1+g2Σ2,1 or I=Λ∖ℬ∗3gΣ1. In both cases, GIΛ is isomorphic to the graph given in Figure 5.
For all these 3 cases, one can easily show that metric dimension ofGIΛ is 2.
Finally, it is required to check all the graphsGIΛ of order six having metric dimension 2. Binyamin et al. [34] proved that if GIΛ=6, then GIΛ is isomorphic to one of the graphs given in Table 1. Now, it is easy to see that all the graphs given in Table 1 have metric dimension 3.Figure 3
GraphsGIΛ When x=5gΣ1 with Λpx=0, ∀p≥2.Figure 4
GraphsGIΛ When x=2gΣ2 with Λpx=0, ∀p≠q2.Figure 5
GraphGIΛ for the remaining two cases.Table 1
GraphGIΛ of order 6 up to isomorphism.
TypeDegree sequenceGraph11,2,3,3,4,522,3,3,4,5,532,3,4,4,4,543,3,4,4,5,553,4,4,4,4,564,4,4,4,5,5



---

*Source: 6697980-2021-02-09.xml*