# Some Indices over a New Algebraic Graph

Authors: Nurten Urlu Özalan
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In this paper, we first introduce a new graphΓN over an extension N of semigroups and after that we study and characterize the spectral properties such as the diameter, girth, maximum and minimum degrees, domination number, chromatic number, clique number, degree sequence, irregularity index, and also perfectness for ΓN. Moreover, we state and prove some important known Zagreb indices on this new graph.


---

## Body

## 1. Introduction and Preliminaries

Semigroups are one of the types of algebra to which the methods of universal algebra are applied. During the last three decades, graph theory has established itself as an important mathematical tool in a wide variety of subjects. One of the several ways to study the algebraic structures in mathematics is to consider the relations between graph theory and semigroup theory known as algebraic graph theory. Cayley graphs of semigroups have been extensively studied, and many interesting results have been obtained (see [1].) On the other hand, zero-divisor graph of a commutative semigroup with zero has also been studied by many authors (for example, see [2]). These developments of algebraic structure indicate that it is important to study the graph of a semigroup.When a new structure appears, it is necessary to investigate the properties. For example, in [3], the author considered a new product and gave some properties on a special product of semigroups (and monoids). Similarly, in [4], we established a new class of semigroups N based on both Rees matrix and completely 0-simple semigroups. We further presented some fundamental properties and finiteness conditions for this new structure. Furthermore, we first showed that N satisfies two important homological properties, namely, Rees short exact sequence and short five lemma. In addition, by defining inversive semigroup varieties of N, we proved that strictly inverse semigroup N is isomorphic to the spined product of (C)-inversive semigroup and the idempotent semigroup of N. Moreover, we gave some consequences of the results to make a detailed classification over N. On the other hand, we proved Green’s theorem over N by showing the existence of Green’s lemma. In this paper, we more deeply investigate the place of N in the literature by means of graph theory. In [5], the authors presented similar study on semidirect products of monoids.Some basic preliminaries, useful notations, and valuable mathematical terminologies needed in what follows are prescribed. Note that a graphG is an order pair VG,EG of a nonempty vertex set VG and an edge set EG. For all undefined notions and notations, we refer the reader to [6].Recall that the girth of a graphG is the length of the shortest cycle in G, if G has a cycle; otherwise, we say the girth of G is ∞. The distance between vertices u and w, denoted by du,w, is the length of a minimal path from u to w. If there is no path from u to w, we say that the distance between u and w is ∞. The diameter of a connected graph G is the maximum distance between two vertices, and it is denoted by diamG.Rees matrix semigroups were first introduced by Rees [7], although they were implicitly present in Suschkewitsch. Let S be a semigroup, let I and J be two index sets, and let P be a J×I matrix with entries from S. The set(1)I×S×J=i,s,j|i∈I,s∈S,j∈J,with multiplication defined by(2)i,s,jk,t,l=i,spjkt,l,is a semigroup. This semigroup is called a Rees matrix semigroup. Now, it is known that the form of elements of the semigroup N is as follows:(3)N=ri,0Gor0S,ckorri,ckor0S,0G|1≤i≤nand1≤j≤m.Let us writeN in more detail.(4)N=ri,ck=ri=0ck≠01≤k≤morri≠0ck=01≤i≤norri≠0ck≠01≤k≤mand1≤j≤morri=0ck=0.Here, everyri and ck are elements of Rees matrix semigroup (MR) and completely 0-simple semigroup (MC), respectively. Actually, we know that the semigroup N consists of the semigroup S and the group G (see [4] for more details). Moreover, we can keep in our mind the diagram in Figure 1 for the semigroup N.Figure 1
The diagram for the semigroupN.We note that index sets mentioned inN are assumed to be single elements and S=m, G=n. Now we give the description of the graph focused in this paper. Let ΓN be graph for the semigroup N.The vertices are all elements ofN, and any two distinct vertices ri,ck and rt,cp are adjacent in case of(i)
ri=rt and ck,cp≠0 or(ii)
ck=cp and ri,rt≠0 or(iii)
ri,ck∗rt,cp=0Example 1.
IfS=0S,s1,s2,s3 and G=0G,g1, then we have(5)N=0S,0G,0S,c1,r1,0G,r1,c1,r2,0G,r2,c1,r3,0G,r3,c1,where r1,r2, and r3 are Rees matrix semigroups created by I and J index sets and the semigroup S. On the other hand, c1 is a completely simple semigroup created by I and J index sets and the group G. The graph of N is as drawn in Figure 2.
One may address three major problems related to graph theory when a new structure emerges:definition, spectral properties for classification, and topological indices of the graph. In this paper, we focus on all of those for the graph ΓN.Figure 2
An example of the graphΓN.


## 2. Spectral Properties ofΓN

In this section, by considering the graphΓN defined in the first section, we will mainly deal with the graph properties, namely, diameter, girth, maximum and minimum degrees, domination number, irregularity index, chromatic number, and clique number.Theorem 1.
IfS≥2 and G≥2, then the diameter of the graph ΓN is 2.Proof.
In the graph of the semigroupN, it is clear that the vertex 0S,0G is adjacent to every vertex. So, the diameter can be figured out by considering the distance between this vertex and one of the other vertices in the vertex set. Therefore, by calculating the eccentricity, any vertex with another neighborhood of a vertex 0S,0G is absolutely considered. We finally get diamΓN=2, as required.Theorem 2.
For the semigroupN, the girth of the graph ΓN is 3.Proof.
By considering the definition ofΓN, the length of the shortest cycle in ΓN is 3. So, the girth of the graph ΓN is 3.The degree of a vertexv is the number of edges incident to v, and it is denoted as degv. Among all degrees, the maximum degree ΔG and the minimum degree δG of G are the number of the largest degree and the number of the smallest degree in G, respectively.Theorem 3.
For the semigroupN, the maximum and minimum degrees of the graph ΓN are(6)ΔΓN=m·n−1andδΓN=m+n−3.Proof.
Let us consider the vertex0S,0G,ri,0G,0S,ci,ri,ck of ΓN. Firstly, we deal with the vertex 0S,0G. Since this vertex is adjacent to every vertex, the degree of 0S,0G is S·G−1. By considering the definition of ΓN, degrees for the both of the vertices ri,0G and 0S,ck are m+n−2. Moreover, the degree of ri,ck is m+n−3. Therefore, the maximum degree of the graph ΓN is m·n−1 and the minimum degree of the graph ΓN is m+n−3.The degree sequence is the list of degree of all the vertices of the graph. This sequence is denoted byDSG for the graph G. In [8], the author defined a new parameter for graphs which is called irregularity index of G and denoted by tG. In fact, irregularity index is the number of distinct terms in the list of degree sequence.Theorem 4.
Letm and n be the orders of the group G and the semigroup S, respectively. The degree sequence and irregularity index of ΓN are given by(7)DSN=m+n−3,m+n−3,…,m+n−3,m+n−2,m+n−2,…,m+n−2,m+n−1,and tG=3, respectively.Proof.
The main idea of the proof is to consider whether the degree of each vertex is the same. In accordance with definition of the graphΓN, the answer is clearly no. We know that the vertices of ΓN are of the form 0S,0G,ri,0G,0S,ck, and ri,ck. Firstly, we consider the vertex 0S,0G. By definition of ΓN, the vertex 0S,0G is adjacent to every vertex. So, the degree of vertex 0S,0G is n·m−1. Similarly, we consider the vertex types of ri,0G and 0S,ck. The degrees of these vertices are same and m+n−2. Finally, the degree of ri,ck is m+n−3 via the definition of ΓN. Therefore, we have DSN=m+n−3,m+n−3,…,m+n−3,m+n−2,m+n−2,…,m+n−2,m+n−1 and the number of distinct terms in the list of DSN is 3. So, tG=3.A subsetD of the vertex set VG of a 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 the smallest dominating set for G (see [6]).Theorem 5.
For the semigroupN, γΓN=1.Proof.
Let us consider the graphΓN. The vertex 0S,0G is adjacent to every vertex. So, the domination number of this graph is 1.
Graph coloring is an assignment of labels, called colors, to the vertices of a graph such that no two adjacent vertices share the same color. The chromatic numberχG of a graph G is the minimal number of colors for which such an assignment is possible. On the other hand, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. A maximum clique of a graph is a clique, such that there is no clique with more vertices. Moreover, the clique number ωG of a graph G is the number of vertices in a maximum clique in G. Clearly, χG≥ωG for every graph G, but equality need not hold. For example, if G is an odd hole (i.e., a hole with an odd number of vertices), then χG=3>2=ωG. A graph is perfect if χG=ωG for every induced subgraph H of G; that is, the chromatic number of H is equal to the maximum size of a clique of H. Bipartite graph is one of the best known examples of perfect graph (see [9]).Let us give the following lemma known as perfect graph theorem of Lovasz [10], originally conjectured by Berge.Lemma 1.
A graph is perfect if and only if its complement is perfect.Theorem 6.
The chromatic number ofΓN is equal to(8)χΓN=m+n−1.Proof.
It is well known that the vertex0S,0G is of maximum degree and ri,0G and 0S,ck are of same degrees. Moreover, these vertices are adjacent to each other due to the definition of ΓN. So, these vertices have a different color. Besides, the types of the vertices ri,ck are adjacent to 0S,0G, but still all the vertices ri,ck are not adjacent to the vertex ri,0G and the vertex 0S,ck; then, the types of the vertices ri,ck can take the same color. So, the vertices taking different colors are considered below.(i)
The vertex0S,0G is unique. So, one color emerges from this vertex.(ii)
The types ofri,0G have m−1 vertices. So, m−1 color emerges from these vertices.(iii)
The types of0S,ck have n−1 vertices. So, n−1 color emerges from these vertices.
Then,(9)χΓN=1+m−1+n−1=m+n−1.Theorem 7.
The clique number ofΓN is equal to(10)ωΓN=m+n−1.Proof.
Now, let us consider the complete subgraphA⊆ΓN. By the definition of ΓN, the vertex set of A is defined as follows:(11)VA=0S,c1,0S,c2,0S,c3,…,0S,ck︸n−1times,r1,0G,r2,0G,r3,0G,…,ri,0G︸m−1times,0S,0G︸1time.
Then,(12)ωΓN=n−1+m−1+1=m+n−1.By keeping in our minds the definition of perfect graphs [10] as depicted and considering in Theorems 6 and 7, we obtain the perfectness of the graph ΓN as in the following corollary.Corollary 1.
The graphΓN is perfect.By using Lemma1, we can also obtain the perfectness of ΓN as in the following result.Corollary 2.
A complement of the graphΓN is perfect.We recall that any graphG is called Berge if no induced subgraph of G is an odd cycle of length of at least five or the complement of one. The following lemma proved by Chudnovsky et al. in [11] figures out the relationship between perfect and Berge graphs. By considering this lemma, we have the following other consequence (Corollary3) of this section.Lemma 2 (see [11]).
A graph is perfect if and only if it is Berge.Corollary 3.
The graphΓN is Berge.As a final note, we may refer [6] for some other properties of perfect graphs which are clearly satisfied for ΓN.


## 3. Zagreb Indices ofΓN

In this section, we give some Zagreb indices of the graphΓN. In order to obtain these results, we need to recall some previously known facts about Zagreb indices.A graph invariant is a number related to a graph which is a structural invariant. The well-known graph invariants are the Zagreb indices. Two of the most important Zagreb indices are called first and second Zagreb indices denoted byM1G and M2G, respectively: (13)M1G=∑u∈VGdGu2,M2G=∑uv∈EGdGudGv.They were first defined by Gutman and Trinajstić in [12]. For various mathematical and chemical studies of these indices, we refer our readers to [13, 14]. Todeschini and Consonni [15] have introduced the multiplicative variants of these additive graph invariants by(14)∏1G=∏u∈VGdGu2,∏2G=∏uv∈EGdGudGv,and called them multiplicative Zagreb indices. In recent years, some novel variants of ordinary Zagreb indices have been introduced and studied, such as Zagreb coindices, multiplicative Zagreb indices, multiplicative sum Zagreb index, and multiplicative Zagreb coindices (see [13, 16–21], for more details). Especially, the first and second Zagreb coindices of graph G are defined [16] in the following:(15)M1¯G=∑uv∉EGdGu+dGv,M2¯G=∑uv∉EGdGudGv.In [21], the authors define the Zagreb coindices and then obtain some fundamental properties of them. We use some of these properties in this paper. Now let us give the two lemmas which are used in this paper.Lemma 3.
(see [16]). Let G be a simple graph on a vertices and b edges. Then,(16)M1¯G=2ba−1−M1G,M2¯G=2b2−M2G−12M1G.Both the first Zagreb index and the second Zagreb index give greater weights to the inner vertices and edges and smaller weights to outer vertices and edges, which opposes intuitive reasoning. Hence, they were amended as follows [22]: for a simple connected graph G, let M1mG=∑v∈VG1/dv2, which was called the first modified Zagreb index, and M2mG=∑uv∈EG1/dudv, which was called the second modified Zagreb index.The hyper-Zagreb index, defined asHZG=∑uv∈EGdu+dv2, was put forward in [23]. In [14], the author established the hyper-Zagreb coindex via hyper-Zagreb index and first Zagreb index.Lemma 4.
(see [14]). Let G be a graph with a vertices and b edges. Then,(17)HZG=FG+2M2G,HZ¯G=4b2+a−2M1G−HZG.It is seen thatFG is the kind of graph invariant. This invariant is vertex-degree based. In [12], the authors defined it as(18)FG=∑v∈VGdGv3.Let us remind a well-known result called by thehandshaking lemma. So, for a graph G, let di be the degree of the ith vertex vi∈VG and e∈EG. Then, we have(19)d1+d2+d3+⋯+dn=2e.Now, let us give the results related to Zagreb indices for the graphΓN.Lemma 5.
A number of vertex for the graphΓN is mn.Proof.
It is known that there are four different types of vertices in this graph. A type of the vertex0S,0G is unique. There are m−1 and n−1 for the types of vertices ri,0G and 0S,ck, respectively. A type of the vertices ri,ck is m−1n−1 times. So, a number of vertex for the graph ΓN is 1+m−1+n−1+mn−m−n+1=mn.Lemma 6.
A number of edge for the graphΓN is mnm+n−2/2.Proof.
By equation (1), it is known that d1+d2+d3+⋯+dn=2e. According to Theorem 3 and Lemma 5,(20)∑v∈VΓNdv=1.mn−1+m−1m+n−2+n−1m+n−2+m−1n−1m+n−3=m2n+mn2−2mn=2e.
Then, a number of edge for the graphΓN is mnm+n−2/2.Theorem 8.
LetΓN be the semigroup graph. Then, the first Zagreb index and second Zagreb index are(21)M1ΓN=mn−12+m+n−23+m+n−32m−1n−1,M2ΓN=m+n−22mn−1+m+2n−5+m+n−3mn−1m−1n−1+m+n−4m+n−3.Proof.
Let us start with the proof of the first Zagreb index. The graph ofΓN has nm vertices (by Lemma 5), and the vertex 0S,0G has mn−1 degree, the vertices 0S,ck and ri,0G have m+n−2 degrees, and the vertex ri,ck has m+n−3 degree.(22)M1ΓN=mn−12+m+n−22m−1+m+n−22n−1+m+n−32m−1n−1=mn−12+m+n−23+m+n−32m−1n−1.
For second Zagreb index, we clearly mention the definition of second Zagreb index for graph in this section. Firstly, we must consider adjacent vertices of the graph, which is as follows.(i)
0S,0G∼ri,0G ⟶ there are m−1 such neighborhoods.(ii)
0S,0G∼0S,ck ⟶ there are n−1 such neighborhoods.(iii)
0S,0G∼ri,ck ⟶ there are m−1n−1 such neighborhoods.(iv)
ri,0G∼rl,0G ⟶ there are m−2 such neighborhoods i≠l.(v)
ri,0G∼0S,ck ⟶ there are n−1 such neighborhoods.(vi)
0S,ck∼0S,cl ⟶ there are n−2 such neighborhoods k≠l.(vii)
ri,ck∼ri,cl ⟶ there are n−1 such neighborhoods k≠l.(viii)
ri,ck∼rl,ck ⟶ there are n−1 such neighborhoods i≠l.(23)M2ΓN=mn−1m+n−2m−1+mn−1m+n−2n−1+mn−1m+n−3m−1n−1+m+n−22m−2+m+n−22n−1+m+n−22n−2+m+n−32n−2+m+n−32m−2=m+n−22mn−1+m+2n−5+m+n−3mn−1m−1n−1+m+n−4m+n−3.Theorem 9.
The first multiplicative Zagreb index and second multiplicative Zagreb index are(24)∏1ΓN=mn−12m+n−22m+2n−4m+n−32m−1n−1,∏2ΓN=mn−1m+n−1m−1mn−1m+n−2n−1mn−1m+n−3m−1n−1m+n−22m+4n−10m+n−32m+2n−8.Proof.
We give the number of vertex and degree of the graphΓN. By definition, first multiplicative Zagreb index is as follows:(25)∏1ΓN=mn−12m+n−22m−1m+n−22n−1m+n−32m−1n−1mn−12m+n−22m+2n−4m+n−32m−1n−1.Second multiplicative Zagreb index is(26)∏2ΓN=πuv∈EΓN=mn−1m+n−1m−1mn−1m+n−2n−1mn−1m+n−3m−1n−1m+n−22m−2m+n−22n−1m+n−22n−2m+n−32n−2m+n−32m−2=mn−1m+n−1m−1mn−1m+n−2n−1mn−1m+n−3m−1n−1m+n−22m+4n−10m+n−32m+2n−8.Theorem 10.
The first Zagreb coindex and second Zagreb coindex are(27)M1¯ΓN=mnm+n−2mn−1−mn−12−m+n−23−m+n−32m−1n−1,M2¯ΓN=2.m2n2m+n−224−m+n−22mn−1+m+2n−5+m+n−3mn−1m−1n−1+m+n−4m+n−3−12mn−12+m+n−23+m+n−32m−1n−1.Proof.
We know that the numbers of vertex and edge for the graphΓN are mn and mnm+n−2/2, respectively, by Lemmas 5 and 6. According to Lemma 3, the first Zagreb coindex is(28)M¯1ΓN=2·mnm+n−22mn−1−mn−12+m+n−23+m+n−32m−1n−1=mnm+n−2mn−1−mn−12−m+n−23−m+n−32m−1n−1.
Similarly, by Lemma3, a second Zagreb coindex is(29)M¯2ΓN=2·m2n2m+n−224−m+n−22mn−1+m+2n−5+m+n−3mn−1m−1n−1+m+n−4m+n−3−12mn−12+m+n−23+m+n−32m−1n−1.Theorem 11.
The first modified Zagreb index and second modified Zagreb index are(30)M1mΓN=1mn−12+m−1m+n−22+n−1m+n−22+m−1n−1m+n−32,M2mΓN=m−1mn−1m+n−2+n−1mn−1m+n−2+m−1n−1mn−1m+n−3+m−2m+n−22+n−1m+n−22+n−2m+n−22+n−2m+n−32+m−2m+n−32.Proof.
The definition of modified Zagreb index is to insert inverse values of the vertex-degrees intoM1G and M2G. Accordingly, the proof is clear.Theorem 12.
The forgotten index is(31)FΓN=mn−13+m+n−24+m+n−33m−1n−1.Proof.
We know that(32)FG=∑v∈VGdGv3.
For the graph ofΓN,(33)FΓN=∑v∈VΓNdGv3=mn−13+m+n−24+m+n−33m−1n−1.Theorem 13.
The hyper-Zagreb index and hyper-Zagreb coindex are(34)HZΓN=mn−13+m+n−24+m+n−33m−1n−1+2m+n−22mn−1+m+2n−5+m+n−3mn−1m−1n−1+m+n−4m+n−3,HZ¯ΓN=m2n2m+n−22+mn−2·mn−12+m+n−23+m+n−32m−1n−1−mn−13+m+n−24+m+n−33m−1n−1+2m+n−22mn−1+m+2n−5.Proof.
We obtain forgotten index and second Zagreb index of the graphΓN in Theorem 12 and 8. By Lemma 4, we clearly have HZΓN and HZ¯ΓN.


## 4. Conclusion

The most important aspect of thinking graph on a new algebraic structure is that the graph reflects new results for both algebraic structure and graph. When a new graph appears, it is important to study some graph properties, namely, diameter, maximum and minimum degrees, girth, degree sequence and irregularity index, domination number, chromatic number, and clique number (in Section2). In this paper, we obtained these results. Furthermore, we gave some important known Zagreb indices (in Section 3).



---

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