# Characterization of Graphs Associated with the Ideal of Numerical Semigroups

Authors: Peng Xu; Muhammad Ahsan Binyamin; Adnan Aslam; Wajid Ali; Hasan Mahmood; Hao Zhou
Journal: Journal of Mathematics
 (2020)

---

## Abstract

LetI be an ideal of a numerical semigroup Λ. We define an undirected graph GIΛ with vertex set vi:i∈Λ∖I∗=Λ∖I−0 and edge set vivj⟺i+j∈I. The aim of this article is to discuss the connectedness, girth, completeness, and some other related properties of the graph GIΛ.


---

## Body

## 1. Introduction and Preliminaries

In mathematics, graph theory plays an important role in understanding the relationship between pair of objects through graphs. Today, graph theory has a number of applications in the field of engineering, computer science, and other sciences (see [1–3]). The idea of linking graph with algebraic structure gave rise to new research in the field of mathematics. This idea explores the interaction between structures of algebraic objects and graphs by using properties of graphs and algebraic structures. In the past, many researchers associated graphs with different algebraic structures (see [4–11]).A graphGVG,EG is an ordered pair with the vertex set VG and the edge set EG. The order and the size of the graph G are the cardinality of its vertex set and edge, respectively. A graph G is connected if for any two vertices u,v∈VG, there is a path connecting u and v. The distance between two vertices u,v∈VG is the length of the shortest path between them and is denoted by du,v. The length of the longest path in G is the diameter of G, denoted by diamG. Length of a shortest cycle in the graph is referred to as the girth of the graph. A graph is complete if for any two vertices, there is an edge between them. A subgraph H of a graph G is a clique if H is a complete graph, and the order of maximal clique is called the clique number of G, denoted by clG. A graph is regular if all of its vertices have the same degree. For more undefined terminologies related to graph theory, see [12–14].Numerical semigroup theory is the study of set of positive integer solutions of diophantine equations (see [15–18]), and this is very useful in the study of algebraic geometry codes (see [19–21]). Let us recall some definitions from the numerical semigroup theory, which we used in the later sections.A subsetΛ⊆ℕ of nonnegative integers is called submonoid if the following holds:(1)
0∈Λ(2)
Ifx,y∈Λ, then x+y∈ΛA submonoidΛ is called numerical semigroup if ℕ∖Λ is finite. The least positive integer in Λ, denoted by mΛ, is known as the multiplicity of the numerical semigroup. The elements of ℕ∖Λ are called the gaps of Λ, and the largest of these gaps is known as the Frobenius number, denoted by FΛ. It is well known that every numerical semigroup is finitely generated; that is, there exist a1,…,at such that Λ=a1,…,at=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 the embedding dimension of numerical semigroup Λ, denoted by eΛ. A subset I of numerical semigroup Λ is ideal (integral ideal) of Λ if I+Λ⊆I (that is, ∀x∈I and s∈Λ, the element x+s is in I). An ideal I is an irreducible ideal if it cannot be written as intersection of two ideals which properly contain it.A connection of graphs with numerical semigroups can be found in [22]. In this paper, we investigated the interplay between the structure of numerical semigroups and graph theoretic properties of specific graphs gained from numerical semigroups. The sketch of this paper is as follows.In Section2, we briefly describe the concept of connectedness, diameter, and girth of GIΛ. In Section 3, we present a necessary and sufficient condition for a graph associated with an ideal of a numerical semigroup to be complete. In Section 4, we discuss the concept of clique number and cut point of GIΛ.


## 2. Connectedness, Diameter, and Girth ofGIΛ

We start this section by showing thatGIΛ is always a connected graph. Also, we show that the diameter of GIΛ is equal or less than 2 and girth of GIΛ is 3.Proposition 1.
LetΛ be a numerical semigroup and I be an ideal of Λ. Then, GIΛ is a connected graph of finite order with at least one vertex of degree ∣Λ∖I∗∣−1.Proof.
ChooseFΛ∈Λ, the Frobenius number, and l∈I, the least element. Then, note that FΛ+l+m∈I for all m≥1. This gives that Λ∖I is always finite, and therefore, Λ∖I∗ is finite. We may assume that n is the largest element of Λ not in I as Λ∖I∗ is finite. This gives that i+n∈I, ∀i∈Λ∖I∗. Therefore, GIΛ is a connected graph of finite order with degree of vn and is equal to ∣Λ∖I∗∣−1.Example 1.
LetΛ=0,3,6,7,9,10,11,12,13,14,… be a numerical semigroup and I=11,12,13,… be an ideal of Λ. Then, Λ∖I∗=3,6,7,9,10 and the graph GIΛ is shown in Figure 1.Figure 1
GraphGI(Λ), where Λ = < 3, 5, 7 > and I = {11, 12, 13, …}.Proposition 2.
LetGIΛ be a graph associated with an ideal I of a numerical semigroup Λ. Then, diamGIΛ≤2. Furthermore, if GIΛ contains a cycle, then grGIΛ≤5.Proof.
Letn∈Λ∖I∗ be the largest element of Λ not in I; then, vn has an edge with every vertex vk, where k∈Λ∖I∗ and k≠n. Therefore, dvn,vk=1. Now, for any two vertices vi and vj, i≠j, we have(1)dvi,vj≤dvi,vn+dvn,vj≤2.
This implies that(2)diamGIΛ≤2.
Moreover, if any undirected graphG has a cycle, then gr G≤2diamG+1 (see [13], Propostion 1.3.2). Therefore, grGIΛ≤5.Lemma 1.
LetGIΛ be a graph associated with an ideal I of a numerical semigroup Λ. If order of GIΛ is 4, then GIΛ must contain a cycle of length 3.Proof.
We may assume thatΛ∖I∗=x1,x2,x3,x4. If GIΛ is complete, then trivially it contains a cycle of length 3; otherwise, there is at least one pair of nonadjacent vertices. We have the following cases:Case_1: ifvx1 and vx2 are nonadjacent, then either x1+x2=x3 or x1+x2=x4. If x1+x2=x3, then there are two more possibilities, either x1+x3=x4 or x2+x3=x4. So, x1+x2=x3 and x1+x3=x4 give x2+x3,x2+x4,andx3+x4∈I. This implies that there is a cycle vx2−vx3−vx4−vx2 of length 3. Also, x1+x2=x3 and x2+x3=x4 give x1+x3,x1+x4,andx3+x4∈I. This implies there is a cycle vx1−vx3−vx4−vx1 of length 3. Now, if x1+x2=x4, then clearly x1+x3,x1+x4,andx3+x4∈I, and therefore, there is a cycle vx1−vx3−vx4−vx1 of length 3.Case_2: ifx1 and x3 are nonadjacent, then x2+x3,x2+x4,andx3+x4∈I, and therefore, there is a cycle vx2−vx3−vx4−vx2 of length 3.Case_3: ifx2 and x3 are nonadjacent, then x1+x3,x1+x4,andx3+x4∈I, and therefore, there is a cycle vx1−vx3−vx4−vx1 of length 3.Proposition 3.
LetGIΛ be a graph associated with an ideal I of a numerical semigroup Λ. If order of GIΛ≥4, then GIΛ must contain a cycle of length 3.Proof.
This follows from Lemma1.Corollary 1.
LetGIΛ be a graph associated with an ideal I of a numerical semigroup Λ. If order of GIΛ≥4, then GIΛ is not a bipartite graph.Corollary 2.
LetGIΛ be a graph associated with an ideal I of a numerical semigroup Λ. If order of GIΛ≥4, then grGIΛ=3.


## 3. Completeness ofGIΛ

In this section, we provide a sufficient and necessary condition forGIΛ to be complete. Moreover, for a given numerical semigroup Λ, we computed the least number of ideals I for which graph GIΛ is complete.Lemma 2.
Any ideal of a numerical semigroupΛ is an intersection of irreducible ideals. Moreover, every irreducible ideal of numerical semigroup Λ is of the form Λ∖Bx, where Bx=y∈Λ:x−y∈Λ, for some x∈Λ.Proof.
For a proof, see [23].Proposition 4.
LetI be an irreducible ideal of a numerical semigroup Λ. If order of GIΛ≥3, then GIΛ cannot be a complete graph.Proof.
SinceI is an irreducible ideal, order of GIΛ=Bx∗ for some x∈Λ. We may assume that Bx∗=x1,…,xn,x, where n≥2. Then, there must exist xi,xj∈Bx∗ for i≠j such that x−xi=xj. This gives xi+xj=x, so there is no edge between vxi and vxj, and therefore, GIΛ is not a complete graph.Example 2.
LetΛ=3,5,7 be a numerical semigroup. Choose 10∈Λ; then, B∗10=3,5,7,10, and therefore, I=Λ∖B∗10=6,8,9,11,… is an irreducible ideal. As B∗10=4, GIΛ is not a complete graph (see Figure 2).Figure 2
GraphGI(Λ), where Λ = < 3, 5, 7 > and I is an irreducible ideal with x = 10.Corollary 3.
LetGIΛ is a graph of order ≥3, associated with an irreducible ideal I of a numerical semigroup Λ. Then, GIΛ cannot be a regular graph.Proof.
This follows from Proposition1 and Proposition 4.Lemma 3.
LetΛ=A, where A=a1,…,ar is the minimal system of generators. Then, for some x∈Λ, Bx=0,ai,2ai,…,x if and only if x is the multiple of exactly one element ai∈A.Proof.
Suppose thatBx=0,ai,2ai,…,x and x is not a multiple of exactly one element of A. Then,Case_1: ifx is a multiple of an element of aj∈A other than ai, then we can assume x=naj. This gives x−aj=n−1aj∈Λ and therefore aj∈Bx, which is not possible.Case_2: ifx is a linear combination of at least two elements ai,aj∈A, then x=sai+raj for some positive integers s and r. Note that x−aj=sai+r−1aj∈Λ. This gives aj∈Bx, which is not possible.
The converse of this statement is straightforward.Theorem 1.
LetI be an ideal of a numerical semigroup Λ such that I=∩1≤j≤nIj, where Ij is an irreducible ideal and n≥2. Then, GIΛ is complete if and only if order of GIjΛ≤2 for each 1≤j≤n.Proof.
LetΛ=A, where A=a1,…,ar is the minimal system of generators. As for each 1≤j≤n, Ij is an irreducible ideal; therefore, we can assume that Ij=Λ∖Bxj for some xj∈Λ. This gives that the set of vertices of GIΛ is vi:i∈Bx1∗∪…∪Bxn∗.
To prove the implication “⇒”, suppose order of GImΛ≥3 for some 1≤m≤n. Then, from Proposition 4, it follows that GImΛ is not a complete graph, so there must exist xi,xj∈Bxm∗ such that xi+xj∈Bxm∗; i.e., there is no edge between vxi and vxj. This gives xi,xj∈Bx1∗∪⋯∪Bxn∗ such that xi+xj∈Bx1∗∪⋯∪Bxn∗, and therefore, GIΛ is not complete.
Now, to prove the implication “⇐”, we suppose on contrary that GIΛ is not a complete graph. Therefore, there exist x,y,z∈Bx1∗∪⋯∪Bxn∗ such that z=x+y. However, the order of GIjΛ≤2 for each 1≤j≤n; therefore, either Bxj∗=1 or Bxj∗=2. This gives that every element of Bx1∗∪⋯∪Bxn∗ is either an element of the minimal system of generators A or twice of some element of A (see Lemma 3). Note that z cannot be an element of A because z=x+y, so the only possibility is that z is twice of some element of A, say z=2as, for some 1≤s≤r. This gives x,y,z∈Bz∗, i.e., Bz∗≥3, which is not possible. Hence, GIΛ is a complete graph.Example 3.
LetΛ=3,5=0,3,5,6,8,9,… be a numerical semigroup. Consider the irreducible ideals I1=Λ∖B3∗, I2=Λ∖B5∗, I3=Λ∖B6∗, I4=Λ∖B10∗, and I5=Λ∖B12∗, where B3∗=3, B5∗=5, B6∗=3,6, B10∗=5,10, and B12∗=3,6,9,12. Let I=I1∩I2∩I3∩I4=8,9,11,… and J=I1∩I2∩I3∩I4∩I5=11,12,… be two ideals of Λ. Then, by Theorem 1, it follows that GIΛ must be a complete graph (see Figure 3) while GJΛ cannot be a complete graph (see Figure 4).Figure 3
GraphGI(Λ), where Λ = <3, 5,> and I = {8, 9, 11, …}.Figure 4
GraphGI(Λ), where Λ = <3, 5,> and I = {11, 12, …}.Proposition 5.
LetΛ=a1,…,an, where n≥3 be a numerical semigroup. Then, there are at least 2n+2n−1 ideals I such that GIΛ is complete.Proof.
We prove it by induction onn. If n=3, then Λ=a1,a2,a3. We have the following cases:Case_1: ifI is irreducible, then the order of GIΛ is B∗x. From Theorem 1, it follows that GIΛ is complete if and only if GIΛ≤2. This gives B∗x=1 or 2. If B∗x=1, then B∗x=a1, a2, or a3, and if B∗x=2, then B∗x=a1,2a1, a2,2a2, or a3,2a3. But, note that B∗x=a2,2a2 and a3,2a3 may or may not exist because there is a possibility that 2a2 and 2a3 may be the multiple of more than one element of Λ or these are linear combination of two or more than two elements of Λ. So, in this case, there are at least 4 irreducible ideals I for which GIΛ is complete.Case_2: now, ifI is not irreducible, then I can be written as an intersection of irreducible ideals. We assume I=∩1≤j≤nIj, where Ij is an irreducible ideal and n≥2. This gives order of GIΛ as B∗x=∪B∗xj. So, if GIΛ is complete, then B∗xj≤2, for all j, and therefore, B∗xj is one of a1,a2,a3,a1,2a1,a2,2a2, and a3,2a3. As a1,a2,a3,anda1,2a1 must exist in irreducible case, the least possibilities for B∗x are a1,a2, a1,a3, a2,a3,a1,a2,2a1, a1,a3,2a1, a1,a2,a3, and a1,a2,a3,2a1. This gives that there are at least 7 reducible ideals for which GIΛ is complete. Moreover, if Λ=I, then GIΛ is an empty graph, which is trivially a complete graph. Hence, there are at least 12=23+22 ideals for which GIΛ is complete.
Now, suppose that, as the induction hypothesis,n≥4 and, whenever, a numerical semigroup, say Λ1, has a1,a2,…,an−1 as a minimal generating set, then there are at least 2n−1+2n−2 ideals J such that GJΛ1 is complete.
Now, letΛ=a1,a2,…,an. Note that a1,a2,…,an=a1,a2,…,an−1∪an. Then, induction hypothesis gives that there are at least 22n−1+2n−2=2n+2n−1 ideals I such that GIΛ is complete.


## 4. Clique Number and Cut Point

In this section, we present some results on clique number and cut point of the graphGIΛ.Proposition 6.
LetGIΛ be a graph associated with an irreducible ideal I of a numerical semigroup Λ. If order of GIΛ is n, then(3)clGIΛ=n2+1,ifnis even,n+12,ifnis odd.Proof.
SinceI is irreducible, the order of GIΛ is exactly Bx∗, for some x∈Λ. Assume that Bx∗=x1,x2,…,xn−1,x. We have the following cases:Case_1: ifBx∗ is even, then the cardinality of the set Bx∗−x is odd, and by definition of Bx, we know that x−x1=xn−1,x−x2=xn−2,…,x−xn/2−1=xn/2+1. This gives that vx1,vxn−1,vx2,vxn−2,…,vxn/2−1,vxn/2+1 are pairs of nonadjacent vertices. As cardinality of Bx∗−x is odd, it must contain an element xn/2=x/2. Note that every element of the set xn/2,xn/2+1,…,xn−1,x is equal or greater than x/2, and therefore, the sum of any two different elements is greater than x. This gives that the graph corresponding to the set xn/2,xn/2+1,…,xn−1,x is a complete graph of maximum possible order.Case_2: ifBx∗ is odd, then the cardinality of the set Bx∗−x is even. In this case, we have x−x1=xn−1,x−x2=xn−2,…,x−xn−1/2=xn+1/2. This gives that vx1,vxn−1,vx2,vxn−2,…,vxn−1/2,vxn+1/2 are pairs of nonadjacent vertices. Note that every element of the set xn+1/2,xn+1/2+1,…,xn−1,x is greater than x/2, and therefore, the sum of any two different elements is greater than x. This gives that the graph corresponding to the set xn+1/2,xn+1/2+1,…,xn−1,x is a complete graph of maximum possible order.Example 4.
LetΛ=3,5 be a numerical semigroup and I=Λ∖B∗16=9,12,14,15,17,… be an irreducible ideal of Λ. Then, Proposition 6 gives that the subset 8,10,11,13,16 of B∗16=3,5,6,8,10,11,13,16 is the maximal clique, and therefore, the clique number of graph GIΛ is 5. The graph GIΛ and its corresponding maximal clique are given in Figures 5 and 6, respectively:Figure 5
GraphGI(Λ), where Λ = <3, 5,> and I is an irreducible ideal with x = 16.Figure 6
Clique of graphGI(Λ) given in Figure 5.Proposition 7.
LetΛ=A be a numerical semigroup, where A=a1,a2,…,an is the minimal system of generators of Λ and GIΛ is a graph associated with an irreducible ideal I=Λ∖B∗x, for some x∈Λ such that the order of GIΛ≥3. Then, vx is the only cut point of GIΛ if and only if B∗x=ai,2ai,…,x for some ai∈A.Proof.
Assume that there exist somey1,…,yk∈B∗x such that yj≠nai, where 1≤n≤m and 1≤j≤k. Then, we have the following cases:Case_1: ifj=1, then clearly y1+nai∈I for all 1≤n≤m; otherwise, y1 is a multiple of ai. This gives that for every two elements x1,x2∈B∗x other than x and y1, we have two different paths vx1−vx−vx2 and vx1−vy1−vx2. This implies that vx is not a cut point of GIΛ.Case_2: ifj>1, then assume that yk∈B∗x is the largest element such that yk≠nai, where 1≤n≤m. Note that yk+y1=x, where y1 is the smallest element of B∗x such that y1≠nai and 1≤n≤m. Then, y+yk∈I, for all y∈B∗x−y1 and y1+m−1ai∈I. This gives that for every two elements x1,x2∈B∗x other than x and yk, we have two different paths, either vx1−vx−vx2 and vx1−vyk−vx2 or vx1−vx−vx2 and vx1−vm−1ai−vyk−vx2. This implies that vx is not a cut point of GIΛ.
Now, ifB∗x=ai,2ai,…,x, then clearly ai+kai∈B∗x∀i≤k≤m−1 and ai+x∈I. This gives that GIΛ−vx has at least two disconnected components and y+x∈I for all y∈B∗x−x. Therefore, x is the only cut point.Example 5.
LetΛ=4,5, be a numerical semigroup and I=Λ∖B∗16 be a irreducible ideal, where B∗16=4,8,12,16. Then, v16 is a cut point of graph GIΛ (see Figures 7 and 8).Figure 7
GraphGI(Λ), where Λ = <4, 5,> and I is an irreducible ideal with x = 16.Figure 8
GraphGI(Λ) − {v16}.


## 5. Conclusion

In this article, graphs associated with ideals of a numerical semigroup have been studied and it has been proved that these graphs are connected. We investigated some properties such as girth, regularity, clique number, and cut point of these graphs. Also, a necessary and sufficient condition has been given for a graph associated with an ideal of a numerical semigroup to be complete.



---

*Source: 6094372-2020-09-07.xml*