# Line Graphs of Monogenic Semigroup Graphs

Authors: Nihat Akgunes; Yasar Nacaroglu; Sedat Pak
Journal: Journal of Mathematics
 (2021)

---

## Abstract

The concept of monogenic semigroup graphsΓSM is firstly introduced by Das et al. (2013) based on zero divisor graphs. In this study, we mainly discuss the some graph properties over the line graph LΓSM of ΓSM. In detail, we prove the existence of graph parameters, namely, radius, diameter, girth, maximum degree, minimum degree, chromatic number, clique number, and domination number over LΓSM.


---

## Body

## 1. Introduction

The history of studying zero-divisor graphs has began over commutative rings by Beck’s paper [1], and then, it is followed over commutative and noncommutative rings by some of the joint papers (cf. [2–4]). After that, DeMeyer et al. [5, 6] studied these graphs over commutative and noncommutative semigroups. Since zero-divisor graphs have taken so much attention, the researchers added a huge number of studies to improve the literature. In [7], the authors introduced monogenic semigroup graphs ΓSM based on actually zero-divisor graphs. In detail, to define ΓSM, the authors first considered a finite multiplicative monogenic semigroup with zero as the set:(1)SM=0,x,x2,x3,…,xn.By considering the definition given in [5], it has been obtained an undirected (zero-divisor) graph ΓSM associated to SM as in the following. The vertices of the graph are labeled by the nonzero zero divisors (in other words, all nonzero element) of SM, and any two distinct vertices xi and xj, where 1≤i,j≤n, are connected by an edge in case xixj=0 with the rule xixj=xi+j=0 if and only if i+j≥n+1. The fundamental spectral properties of graph ΓSM, such as the diameter, girth, maximum and minimum degree, chromatic number, clique number, degree sequence, irregularity index, and dominating number, are presented in [7]. Furthermore, in [8], first and second Zagreb indices, Randić index, geometric-arithmetic index, and atom-bond connectivity index, Wiener index, Harary index, first and second Zagreb eccentricity indices, eccentric connectivity index, and the degree distance which emphasize the importance of graph ΓSM have been studied.It is known that the line graphLG of G is a graph whose vertices are the edges of G, and any two vertices are incident if and only if they have a common end vertex in G. Although line graphs were firstly introduced by the papers [9, 10], the details of these studies started by Harary [11] and after that by Harary (Chapter 8 in [12]). In fact the line graph is an active topic of research studies at this moment. For example, some topological indices of line graphs have been considered in [13, 14].In Section2, we will mainly deal with the special parameters, namely, radius, diameter, girth, maximum and minimum degree, domination number, and chromatic and clique numbers over the line graph LΓSM of monogenic semigroup graph ΓSM associated with SM as given in (1). We note that [15] will be followed for unexplained terminology and notation in this paper.


## 2. Main Results

In this part, our aim is to reach previously mentioned goals. At this point, we remind that, for any simple graphG, the graph properties such as radius, diameter, and girth are obtained by calculating the distance between any two vertices or the total number of whole vertices. So, our proofs will be based on this idea.Theeccentricity of a vertex v, denoted by eccv, in a connected graph G is the maximum distance between v and any other vertex u of G (for a disconnected graph, all vertices are defined to have infinite eccentricity). It is clear that diamG is equal to the maximum eccentricity among all vertices of G. On the contrary, the minimum eccentricity is called the radius [16, 17] of G and denoted by(2)radG=minu∈EGmaxv∈EGdGu,v.Theorem 1.
LetG=ΓSM be a monogenic semigroup graph. Then, the radius of the line graph LG is given by(3)rLG=1,3≤n≤5,2,n≥6.Proof.
We can easily see that the result is true forn=2,3,4 by Figure 1. So, let us consider n≥6, and let us take into account any two vertices xi1,xj1 and xi2,xj2 from the graph LG. By the definition of G, we have i1+j1>n and i2+j2>n, since xi1xj1,xi2xj2∈EG.
Ifxi1,xj1∩xi2,xj2=1, then dxi1,xj1,xi2,xj2=1.
Ifxi1,xj1∩xi2,xj2=0, then dxi1,xj1,xi2,xj2=1 since xi1,xj1∼xi1,xj2∼xi2,xj2.
So, we obtaineccxi,xj=2 for all xi,xj∈VLG. Thus, LG is a 2-self-centered graph for n≥6.
Hence, the result is obtained.Figure 1
Line graphsΓSM for n=3,4,5.It is known that thediameter of G is defined by the set(4)diamG=supdx,y:xandyare vertices ofG.Theorem 2.
LetG=ΓSM be a monogenic semigroup graph. Then, the diameter of LG is(5)DLG=1,n=3,2,n≥4.Proof.
The proof can be obtained in a similar way as in the proof of Theorem1.We recall that thegirth of a graph G is the length of a shortest cycle contained in G. Moreover, the girth is defined to be infinity if G does not contain any cycle.Theorem 3.
For a monogenic semigroup graphG=ΓSM, the girth of line graph LG is 3.Proof.
SinceLG≅K2 for n=3, we have girthLG=∞. So, we assume that n≥4 which implies the set A=xn,xn−1,xn,xn−2,xn−1,xn−2 is a complete subgraph of LG. Hence, girthLG=3, as required.Themaximum degreeΔ of G is the number of the largest degree in G, and the minimum degreeδ of G is the number of the smallest degree in G (see, for instance, [15]). According to these reminders, we can state and prove the following theorem in terms of the line graph.Theorem 4.
LetG=ΓSM be a monogenic semigroup graph. Then, ΔLG=2n−5.Proof.
We know thatde=du+dv−2 for e=uv∈EG. From definition, the monogenic semigroup graph ΓSM, we have 1=dx<dx2<⋯<dxn/2=dxn/2+1<⋯<dxn=n−1. Therefore, the vertex of maximum degree in LG must be the vertex xn,xn−1. As a result, we have(6)ΔLG=dxn,xn−1=dxn+dxn−1−2=n−1+n−2−2=2n−5,as required.Theorem 5.
LetG=ΓSM be a monogenic semigroup graph. Then, δLG=n−2.Proof.
By definition of the degree sequences of monogenic semigroup graphs in the studies [7, 8], we obtain that the set vertices with minimum degree are(7)x,xn,x2,xn−1,…,xn/2,xn/2+1,nis even,x,xn,x2,xn−1,…,xn/2,xn/2+2,xn/2+1,xn/2+2,nis odd.
Therefore, we have(8)δLG=dx,xn=dx+dxn−2=1+n−1−2=n−2.
Hence, we get the proof.A subsetD of the vertex set VG of any graph G is called a dominating set if every vertex VG\D is joined to at least one vertex of D by an edge. Additionally, the domination numberγG is the number of vertices in a smallest dominating set for G (we may refer [15] for the fundamentals of domination number).Theorem 6.
LetG=ΓSM be a monogenic semigroup graph. The domination number of LG is(9)γLG=1,3≤n≤5,k+1,4k+2≤n≤4k+5k∈ℤ+.Proof.
Let us consider the setA=xn,xn−1,xn−2,xn−3,…,xm+1,xm⊂VLG, where m=⌈n/2⌉ or m=⌈n/2⌉+1. In fact, A is the domination set in VLG.Case 1: supposem=⌈n/2⌉:(10)n=4k+2⇒A=n−n/2+12+1=4k+2−2k+22+1=k+1,n=4k+3⇒A=n−n/2+12+1=4k+3−2k+32+1=k+1,n=4k+4⇒A=n−n/2+12+1=4k+4−2k+32+1=k+32∉ℤ,n=4k+5⇒A=n−n/2+12+1=4k+5−2k+42+1=k+32∉ℤ.Case 2: now, supposem=⌈n/2⌉+1:(11)n=4k+4⇒A=n−n/2+22+1=4k+4−2k+42+1=k+1,n=4k+5⇒A=n−n/2+12+1=4k+5−2k+52+1=k+1.
The above steps complete the proof.Basically, the coloring of any graphG is to be an assignment of colors (elements of some set) to the vertices of G, one color to each vertex, so that adjacent vertices are assigned distinct colors. If n different colors are used, then the coloring is referred to as an n- coloring. If there exists an n-coloring of G, then G is called n-colorable. The minimum number n for which G is n-colorable is called the chromatic number of G and is denoted by χG.In addition, there exists another graph parameter, namely, theclique of a graph G. In fact, depending on the vertices, each of the maximal complete subgraphs of G is called a clique. Moreover, the largest number of vertices in any clique of G is called the clique number and denoted by ωG. In general, by [15], it is well known that χG≥ωG for any graph G. For every induced subgraph K of G, if χK=ωK holds, then G is called a perfect graph [18].Theorem 7.
LetG=ΓSM be a monogenic semigroup graph. Then, ωLG=n−1.Proof.
Due to the definition ofLG, if the vertex xi,xj is adjacent to the vertex xt,xl, then xi,xj∩xt,xl=1. Therefore, the vertex sets of complete graphs in LG must be the form of(12)A=xi,xj:j∈Z+,i+j≥n+1,xi∈VG.
So, since the vertex with maximum degree inG is xn, the maximum complete subgraph in LG is the subgraph with vertex set A, where(13)A=xn,x,xn,x2,…,xn,xn−1,such that the number of elements in it is n−1. Thus, ωLG=n−1, as required.Theorem 8.
For a monogenic semigroup graphG=ΓSM, the chromatic number of line graph of G is determined by χLG=n−1.Proof.
Since the setS=xn,x,xn,x2,…,xn,xn−1 is the complete subgraph of LG, we must paint each vertex in this set with a different color. That means we need to use n−1 colors for this set S. The graph LG has at least one vertex xn,xk that is not adjacent to xi,xj for all of the vertices in LG, where xi,xj∉S. Therefore, we can use one of the colors which used in the set S for the vertex xi,xj∉S. Thus, χLG=n−1, as required.Example 1.
The graph is given in Figure2.Figure 2
Line graph ofΓSM for n=8.Let us consider the semigroup(14)SM=x,x2,x3,x4,x5,x6,x7,x8.Now, by considering the graphLΓSM as drawn in Figure 2, we can list the following results as example:(i)
radLΓSM=2 (obtained by Theorem 1)(ii)
diamLΓSM=2 (obtained by Theorem 2)(iii)
girthLΓSM=3 (obtained by Theorem 3)(iv)
ΔLΓSM=11 (obtained by Theorem 4)(v)
δLΓSM=6 (obtained by Theorem 5)(vi)
γLΓSM=2 (obtained by Theorem 6)(vii)
χLΓSM=7 (obtained by Theorem 7)(viii)
ωLΓSM=7 (obtained by Theorem 8)


## 3. Conclusions

The aim of the study is to investigate the concept of monogenic semigroup graphsΓSM, which is firstly introduced by Das et al. [7], based on zero-divisor graphs. We examine the some graph properties over the line graph LΓSM of ΓSM. The existences of graph parameters, namely, radius, diameter, girth, maximum degree, minimum degree, chromatic number, clique number, and domination number over LΓSM are proved, respectively.



---

*Source: 6630011-2021-04-17.xml*