A STUDY ON GRAPHS OF RINGS

A STUDY ON GRAPHS OF RINGS

LAU ZHOU SHENG

UNIVERSITI TUNKU ABDUL RAHMAN

A STUDY ON GRAPHS OF RINGS

By

LAU ZHOU SHENG

A project report submitted in partial fulfilment of the requirements for the award of Bachelor of Science (Hons.)

Applied Mathematics With Computing

Faculty of Engineering and Science Universiti Tunku Abdul Rahman

APRIL 2019

D ECLARATION O F O RIGINALITY

I hereby declare that this project report entitled"A study on graphs of rings" is my own work except for citations and quotations which have been duly acknowledged. I also declare that it has not been previously and concurrently submitted for any other degree or award at UTAR or other institutions.

Signature :

Name :

ID No. :

Date :

ii

A PPROVAL FOR S UBMISSION

I certify that this project report entitled"A study on graphs of rings"was prepared byLAU ZHOU SHENGhas met the required standard for submission in partial ful- filment of the requirements for the award of Bachelor of Science (Hons.) Applied Mathematics With Computing at Universiti Tunku Abdul Rahman.

Approved by,

Signature :

Supervisor :

Date :

iii

The copyright of this report belongs to the author under the terms of the copyright Act 1987 as qualified by Intellectual Property Policy of University Tunku Abdul Rahman.

Due acknowledgement shall always be made of the use of any material contained in, or derived from, this report.

2019, LAU ZHOU SHENG. All rights reserved.c

iv

A CKNOWLEDGEMENTS

In the preparation of this project, a lot of people have contributed upon this completion.

Upon the completion of this project, I would like to express my gratitude to those who have directly or indirectly provided me some useful guidance in this project. Firstly, I would like to express my utmost gratitude to my supervisor, Dr. Qua Kiat Tat for pro- viding me numerous consultations and excellent guidelines throughout the completion of this project. In addition, a heartfully thanks to my family, who always have been the source of inspiration throughout this process of completion. Besides, I am very thank- ful to my friends who made valuable comments and suggestions on my paper and also have given me vital advices which lead to the smooth finishing of this research project.

LAU ZHOU SHENG

v

A STUDY ON GRAPHS OF RINGS

LAU ZHOU SHENG

ABSTRACT

In this project, we are studied about the connection between ring and graph theory.

This project will involve some knowledge on ring and graph theories. We said a ring R satisfied the properties which are abelian group under addition and closed under multiplication operation. On the other hand, graph theory is a study of the graph which made up of vertices, edges and its properties. The relationship between commutative ring and graph theory were firstly introduced by Beck in 1988. Later, N.Ashrafi(2010) has carried a research on unit graphs associated with rings. Letx andy be arbitrary vertices inR, such thatxandyare adjacent if and only ifx+yis a unit inR. Besides, an elementxis said to be clean if there exists an idempotente ∈ Rsuch thatx−eis a unit inR. Clean rings is firstly defined by Nicholson in 1977. In 2013, Diesel(2013) has introduced nil clean rings and strongly nil clean rings. A ringRis called nil clean ring if for eachx ∈ Rsuch thatx =n+e, for some idempotente ∈R and nilpotent n ∈ R. Further later, Danchev(2015) has introduced weakly nil clean ring.If r ∈ R and there exists an idempotent e ∈ R and nilpotentn ∈ R such that r = n±e. In 2017, Basnet(2017) conducted a research on nil clean ring with graph. He denoted nil clean graph of ringR as G_N(R). Letx and y to be distinct vertices of elements from nil clean ring R, such that x adjacent to y if and only if x+y is a nil clean element in R. The g(x)-nil clean is firstly introduced by L.Fan(2008). An element r ∈ Ris calledg(x)-nil clean ifr = n+sfor some nilpotentn ∈ Rands ∈R such thatg(s) = 0, whereg(x) ∈ Z(R)[x]. We then conduct a research on specifically on g(x) =x²−2x, which isx(x−2)-nil clean graph of ring. LetRbeg(x)-nil clean ring whereg(x) = x(x−2)andpandq to be distinct vertices of elements fromR, such thatpis adjacent toqif and only ifp+q∈Rfor some nilpotentpandg(q) = 0. In this project, we generalized the properties ofg(x)-nil clean graph such as connectedness, completeness, cycle, path and diameter and the adjacency matrix.

vi

T ABLE OF C ONTENTS

TITLE i

DECLARATION OF ORIGINALITY ii

APPROVAL FOR SUBMISSION iii

ACKNOWLEDGEMENTS v

ABSTRACT vi

LIST OF FIGURES viii

LIST OF TABLES x

CHAPTER 1 Introduction 1

1-1 Objectives . . . 1

1-2 Project Scopes . . . 2

1-3 Planning . . . 2

CHAPTER 2 Literature Review 5 CHAPTER 3 Preliminary Results 10 3-1 Methodology . . . 10

3-2 Some properties of nil-clean graphs . . . 10

3-2-1 Invariants of nil clean graphs . . . 13

CHAPTER 4 g(x)-nil clean graph 20 4-1 Introduction . . . 20

4-2 Onx(x−2)-nil clean graphs . . . 20

4-3 Some properties ofg(x)-nil clean graph . . . 28

4-3-1 Invariants ofg(x)-nil clean graphs . . . 29

CHAPTER 5 Conclusion 59

References 60

Appendix 60

vii

L IST OF F IGURES

1 Graph with4and6vertices with unique edges for every vertices . . 6

2 Graph with4and6vertices with multiple edges for every vertices . 6 3 Nil clean graph ofGF(25) . . . 7

4 Nil clean graph ofGF(27) . . . 8

5 Part of Nil clean graph ofGF(25) . . . 9

6 Nil clean graph withxelements includingx . . . 11

7 Nil clean graph withxelements excludingx. . . 11

8 Girth ofG_N(R)with non trivial nilpotent . . . 14

9 Girth ofG_N(R)with non trivial idempotent . . . 14

10 Nil clean graph ofZp . . . 14

11 Nil clean graph ofGF(p^k) . . . 15

12 Bipartite nil clean graph ofGF(p^k) . . . 16

13 G_N(R)withn+ 1elements . . . 17

14 Nil clean graph of elementsnande . . . 18

15 g(x)-nil clean graph ofGF(25) . . . 21

16 g(x)-nil clean graph ofGF(27) . . . 22

17 g(x)-nil clean graph ofGF(49) . . . 23

18 g(x)-nil clean graph ofZ3 toZ34 . . . 27

19 g(x)-nil clean graph withxelements includingx . . . 28

20 g(x)-nil clean graph withxelements excludingx . . . 29

21 disconnected path graph forg(x)-nil clean graph ofZ^2k . . . 30

22 path graph forg(x)-nil clean graph ofZ2k+1 . . . 30

23 hamiltonian cycle forg(x)-nil clean graph ofZ^2k wherek = 2a . . 31

24 g(x)-nil clean graph ofZn . . . 32

25 g(x)-nil clean graph ofZ2p^k . . . 33

26 disconnected graph which build up of twoK₈ . . . 46

27 disconnected graph which build up of twoK₁₆ . . . 49

28 disconnected graph which build up of oneK₅ and oneK₄ . . . 52 viii

LIST OF FIGURES ix

29 disconnected graph which build up of oneK₆ and oneK₅ . . . 54 30 disconnected graph that build up of twoK₅ and twoK₄ . . . 57 31 disconnected graph that build up of twoK₆ and twoK₅ . . . 58

L IST OF T ABLES

1 Plan for Project I . . . 3 2 Plan for Project II . . . 4 3 All combination ofd(a, b) . . . 18

x

C HAPTER 1: I NTRODUCTION

A Ring R is a set with 2operations, addition and multiplication, (R,+,·). Besides that, R is also satisfied 2 important properties which is abelian group under addition and closed under multiplicative. We note that an abelian group closed under addition, (R,+), indicates that the ringRis closed under addition and every element has an ad- ditive inverse. Furthermore, a ring is closed under multiplicative property. Moreover, in the multiplicative property it fulfils the properties of multiplication are associative and distributive. All the rings we considered are commutative with identity.

A graph is defined as to be a ordered pair of (V, E), where V is the finite set of vertices or points of the graph and E is set of unordered pair of elements of V that called edges or lines. For example, letV = {1,2,3,4}, if it exists an edges or a line between vertices 1 and3, thenE will be {(1,3)} or{(3,1)}, and will be written as E = {(1,3)}orE = {(3,1)}. To avoid ambiguity, this type of graph can be called undirected graph. For illustration, we consider the graph below.

In this project, we focus on the study of the relationship between commutative nil clean rings and its graph properties (in Basnet(2017)). We note that girth, diameter, chromatic index and other related graph properties will be the parts of this research studies in the project that related to graph theory.

1-1 Objectives

In project I, we will be learning some basic knowledges on ring theory and graph theory. Moreover, the main task of this project is to learn and understand the proving methods in the paper by Basnet(2017) on nil clean graph of rings.

In project II, we will be applying the knowledge and methods of proving from the paper by Basnet(2017) on nil clean graph of rings into other type of ring. In this project, 1

Chapter 1. Introduction 2

we will be applying the knowledge on x(x−2)-nil clean graph of rings with some extension of other knowledges by using the appropriate methods from Basnet(2017) on nil clean graph of rings.

1-2 Project Scopes

In this project I, we will focus on the property of the nil clean graph of rings and its relationship with the graph properties. For example, girth of graphs, chromatic index of graphs and diameter of graphs which related to the graph theory.

In project II, we will focus on the properties of other type of rings, specifically x(x−2)-nil clean graph of rings, and its relationship with the graph properties. In this project, we have investigate about the properties of graph which related to graph theory such as connectedness of graphs, completeness of graphs, paths and cycles of graphs and diameter of graphs with the extension of properties of adjacency matrix of thex(x−2)-nil clean graph of rings.

1-3 Planning

The following Table 1 and Table 2 show the action plan for project I and project II.

The highlighted part represented the tasks that carried out during the particular week.

The main focus in Project I is reading and collecting the research materials.

Besides, Project I provides a good opportunity in learning the proving methods and skill of writing from published research paper, in this project we will be referencing from the paper published by Basnet(2017) on nil clean graph of rings, that will be helpful in our Project II.

Furthermore, in project II, we continue our research on a different structured rings with the application of the proving methods that we have learn from the Basnet(2017) on nil clean graph of rings. With the help of the existing theorems and lemmas in the Bastnet(2017) on nil clean graph of rings, we are able to have some extensions of our own theorems and lemmas in the continuation of this project.

Chapter 1. Introduction 3

T ask W eek 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Re gistration for Project Submission of biweekly report Reading and collecting research materials Study on literature re vie w Mock presentation for proposal Submission of proposal Analyse research findings Mock presentation of interim report Submission of interim report Oral presentation of Project I

Chapter 1. Introduction 4

T ask W eek 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Continuation of Project I Collecting and reading research materials Submission of Mid- Semester Monitoring form Preparation of project poster Submission of project poster Submission of final project Oral presentation of Project II

C HAPTER 2: L ITERATURE R EVIEW

LetG(R)be an undirected graph, letV(G)be the set of vertices and letE(G)be the set of edges. If xandyinV(G), and represent elements in Rand edges between the points will have an edge if an only ifxy= 0. The relationships between a commutative ring and graph theory are first introduced by Beck (in Beck(1988)). In this paper, Beck has presented the idea of coloring of a commutative rings.

Later, N.Ashrafi(2010) has carried a research on unit graphs associated with rings.

LetG(R)denotes an unit graph with a set of vertices comes from the set elements of R. Letx and y be arbitrary distinct vertices from R, such that xand y are adjacent if and only if x +y is a unit of R. In addition, N.Ashrafi(2010) also investigated other properties of graph such as connectedness, chromatic index, diameter, girth and planarity ofG(R).

Let the sets of idempotents and nilpotents of R to be denoted by Idem(R) and N il(R), respectively. Nicholson(1977) has defined that an element x in a ring R is said to be clean if there exist an e ∈ Idem(R) such thatx−e is a unit ofR. Later in 2013, Diesel(2013) introduced a new variants, nil clean rings and strongly nil clean rings. A ringRis called nil clean ring if for eachx∈Rsuch thatx=n+e, for some n ∈N il(R)ande∈Idem(R).

Further later in 2015, Danchev(2015) generalized the notion of nil clean ring into weakly nil clean ring. An elementr ∈ R is called weakly nil clean if there exists an e∈Idem(R)andn∈N il(R)such thatr =n+eorr =n−e.

Furthermore, in 2017, Basnet(2017) did a research on a relationship between nil clean ring and graph. In the paper, Basnet(2017) denoted a nil clean graph byG_N(R), let the set of nil clean elements denote byN(R). He further investigates the properties of graph ofG_N(R), such as girth, diameter, dominating sets and other related proper- ties. Letxandyto be distinct vertices of the elements from nil clean ringR, such that xadjacent toy if and only ifx+y ∈ N(R). In the same year, Basnet(2017) carried out another research on the relationship between weakly nil clean ring and graph. The weakly nil clean graph denoted byG_{W N}(R)and let a set of weakly nil clean elements denote by W N(R). If x and y to be the distinct vertices of the elements from the

5

Chapter 2. Literature Review 6

weakly nil clean ring R such thatx adjacent to yif and only if x+y ∈ W N(R) or x−y∈W N(R).

On the other hand, there are some notations and definition used in this project. Let G denote the graph, for any x ∈ V(G), the degree of x denotes by deg(x) which defined as the number of edges that connected tox. Besides, the neighbours set ofxis denoted asN_G(x) := {y ∈V(G)|yis adjacent tox}and the setN_G[x] =N_G(x)∪{x}.

Next, a complete graph is a simple undirected graph which have no loops and every distinct vertices are connected by a unique edges. For illustration, we consider the graphs below.

v₂ v₃

v₄ v₁

v₇ v₈

v₁₀ v₅

v₆ v₉

Figure 1: Graph with4and6vertices with unique edges for every vertices

v₁₂ v₁₃

v₁₄ v₁₁

v₁₇ v₁₈

v₂₀ v₁₅

v16 v19

Figure 2: Graph with4and6vertices with multiple edges for every vertices

Chapter 2. Literature Review 7

From the graphs above, we can see that every vertices in Figure 1 have an unique edges connected to it, for example, only have one edge betweenv₂ and v₃. So, Figure 1 is a complete graph. However, Figure 2 is not a complete graph because there exists at least one vertices that have at least one edges connected to it, for example, there are multiple edges connected betweenv₆andv₇.

A nil clean graph of a ringR, denoted byG_N(R), is defined by settingRas vertex set and 2 distinct vertices x and y are adjacent ifx+y is a nil clean element in R.

Moreover, loops not considered. For illustration, we consider GF(25) and GF(27) which is a finite field with25and27elements.

GF(25)∼=Z5[x]/hx²+x+ 1i

={ax+b+hx²+x+ 1i:a, b∈Z5}

Letβ =x+hx²+x+ 1i. ThenGF(25) ={0,1,2,3,4, β,2β,3β,4β,1 +β,2 +β,3 + β,4 +β,1 + 2β,2 + 2β,3 + 2β,4 + 2β,1 + 3β,2 + 3β,3 + 3β,4 + 3β,1 + 4β,2 + 4β,3 + 4β,4 + 4β}

0 1 4 2 3

β 4β+ 1 β+ 4 4β+ 2 β+ 3

4β β+ 1 4β+ 4 β+ 2 4β+ 3

2β 3β+ 1 2β+ 4 3β+ 2 2β+ 3

3β 2β+ 1 3β+ 4 2β+ 2 3β+ 3

Figure 3: Nil clean graph ofGF(25)

Chapter 2. Literature Review 8

GF(27) ∼=Z3[x]/hx³+ 2x² + 1i

={ax²+bx+c+hx³+ 2x²+ 1i:a, b, c∈Z3}

Letγ =x²+hx³+2x²+1iandδ=x+hx³+2x²+1i. ThenGF(27) ={0,1,2, δ, δ+ 1, δ+2,2δ,2δ+1,2δ+2, γ, γ+1, γ+2, γ+δ, γ+δ+1, γ+δ+2, γ+2δ, γ+2δ+1, γ+ 2δ+2,2γ,2γ+1,2γ+2,2γ+δ,2γ+δ+1,2γ+δ+2,2γ+2δ,2γ+2δ+1,2γ+2δ+2}

0 1 2

δ 2δ+ 1 δ+ 2

2δ δ+ 1 2δ+ 2

γ 2γ+ 1 γ+ 2

2γ γ+ 1 2γ+ 2

γ+δ 2γ+ 2δ+ 1 γ+δ+ 2

2γ+ 2δ γ+δ+ 1 2γ+ 2δ+ 2

2γ+δ γ + 2δ+ 1 2γ+δ+ 2

γ+ 2δ 2γ+δ+ 1 γ+ 2δ+ 2 Figure 4: Nil clean graph ofGF(27)

A girth is the shortest cycle that can be found in the graph. For illustration, we consider the Nil clean graph ofGF(25)from Figure 3 andGF(27)from from Figure 4. From the Nil clean graph ofGF(25), it has the shortest cycle of10cycles. On the other hand, Nil clean graph ofGF(27)has the shortest cycle of 6cycles. Therefore, the girth ofGF(25)is10and the girth ofGF(27)is6.

Chromatic index ofG_N(R),χ⁰(G_N(R)), is the minimum number of colours needed forE(GN(R))such that ife, f ∈E(GN(R))andeandfare adjacent, then colour ofe

Chapter 2. Literature Review 9

will not same as the colour off. Let∆be the maximum vertex degree ofG_N(R), then Vizings theorem says that∆≤χ⁰(G_N(R))≤∆ + 1; graphs that satisfiedχ⁰(G) = ∆ are called graphs of class1, those that satisfiedχ⁰(G) = ∆ + 1are called graph of class 2. For illustration, we consider part of the nil clean graph of GF(25) with multiple edges connected between vertices.

0 1

4

2 3

e₂

e₁

e₄

e₃

Figure 5: Part of Nil clean graph ofGF(25)

From the figure above, we notice that vertex2have3edges connected to it,e₁,e₂ ande3, this means the3edges are adjacent to each other. So, edgese1, e2 ande3 will not have the same colour. However, edgese₁ande₄can have the same colour because they are not adjacent to each other. Next, according to Vizings Theorem, the maximum vertex degree will be vertices0and1which have a vertex degree of6. So,∆ = 6, and the graph satisfies6≤χ⁰(G)≤7.

The diameter of the G_N(R)is the shortest path between 2vertices and if x, y ∈ V(GN(R)) and the shortest path between x and y is denoted by d(x, y). If there is no path betweenx andy is said thatd(x, y) = ∞. Thediam(G_N(R))indicates the maximum of distances of each pair of distinct vertices inGN(R).

C HAPTER 3: P RELIMINARY R ESULTS

3-1 Methodology

Preliminary methods will involve reading and understanding of various concepts in ring theory. This will be followed by reading of the research article Basnet (2017) and understanding of techniques used by others. The main work on research problems, which will form the contain of this project, will involve analytical thinking. Besides, in the construction of graphs of rings, we will be using MATLAB as our primary tool.

3-2 Some properties of nil-clean graphs

In the following, we study and investigate on the properties of nil-clean graphs.

Theorem 3.1 The nil clean graphG_N(R)is a complete graph if and only ifRis a nil clean ring.

Proof: (⇒): LetG_N(R)be a complete nil clean graph of ringR. Then it implies that for allr∈Rarenil clean elements. Without lose of generality ofnil clean elements, there exists one path fromris connected to0such thatr =r+ 0which is nil clean, henceRis nil clean.

(⇐): Conversely, letRbe a nil clean ring. To form a graph from theR, let the arbitrary elementsx, y ∈Randxandyare connected if and only ifx+yis anil clean element.

So, this implies that every pairs of distinct element r ∈ R must have a unique edges and it form the complete nil clean graphGN(R).

Lemma 3.1 LetG_N(R) be the nil clean graph of a ringR. For x ∈ R we have the following:

(I) If2xis nil clean, thendeg(x) =|N C(R)| −1.

(II) If2xis not nil clean, thendeg(x) =|N C(R)|.

Proof: Letx ∈R, but clearlyx+R =R. Then for everyy∈ N C(R), there exists a unique elementx_y ∈Rsuch thatx+x_y =y. Thus, we havedeg(x)≤ |N C(R)|

10

Chapter 3. Preliminary Results 11

For (I): Now, we let{x₁, x₂, x₃, ..., x} ⊆ R and {x₁ +x, x₂ +x, x₃ +x, ...,2x} ⊆ N C(R). Since we are not considering any loops, we illustrate the graph in the follow- ing:

x x₁

x2

x3 x

Figure 6: Nil clean graph withxelements includingx

By the definition of N_GN(R)(x) = {y ∈ V(GN(R))|yis adjacent tox}, we know that y = {1,2,3, ..., x}. We have deg(x) = |N_GN(R)(x)| = |N_GN(R)[x]| − 1 =

|N C(R)| −1

For(II): Now, we let{x₁, x₂, x₃, ..., x_y, x} ⊆Rand{x₁+x, x₂+x, x₃+x, ..., x+x_y} ⊆ N C(R)but2x /∈N C(R). Since we are not considering any loops, we have

x x₁

x₂

x₃ x_y

x

Figure 7: Nil clean graph withxelements excludingx

From the definition ofN_GN(R)(x) = {y∈V(G_N(R))|yis adjacent tox}, we know thaty ={x₁, x₂, x₃, ..., x_y}. We havedeg(x) =|N_GN(R)(x)|=|N C(R)|

Lemma 3.2 A ringRis a finite commutative reduced ring with no non trivial idempo- tents if and only ifRis a finite fields.

Proof: LetRbe afinite commutative reduced ring. This implies thatRhasno non- zero nilpotent element. IfR is a finite commutative reduced ring with no non trivial idempotents implies nilpotent is0and idempotents are0and1.

Chapter 3. Preliminary Results 12

(⇒): Let06=x ∈R. We have a setA ={x^k :k ∈ N}is a finite set. Therefore there existsm > lsuch thatx^l =x^m. We illustrate the example in the following.

Example 1 LetZ5 ={0,1,2,3,4}, since0is too obvious to be calculate, so we ignore 0 from the set. So, Z5 = {1,2,3,4}. Let x = 3, then there exists m > l such that x^l =x^m. We letm= 5andl = 1.

So,

3¹ = 3 mod 5 = 3

3⁵ = 243 mod 5 = 3 mod 5 = 3

Therefore,

3¹ = 3⁵

Note that:

x^l=x^m

=x^m+l−l

=x^m−l·x^l

=x^m−l·x^m

=x^{(2m−l)−l+l}

=x^2m−l−l·x^l

=x^2(m−l)·x^m

=x(3m−2l)−l+l

=x^3(m−l)·x^l ...

=x^k(m−l)+l, k ∈N (3.1)

Chapter 3. Preliminary Results 13

Now we have:

[x^l(m−l)]² =x^l(m−l)·x^l(m−l)

=xl(m−l)+l(m−l)+l−l

=x^l(m−l)+1·x^l(m−l)−1

=x^l·x^l(m−l)−l (From (3.1):x^l=x^k(m−l)+l)

=x^l(m−l)

which indicatex^l(m−l) ∈Idem(R). Thus,x^l(m−l) = 1. This gives thatxis a unit inR.

Since we know thatx^l(m−l) = 1, we also know thatx^l·x^l(m−l)−l = 1, so this indicates thatx^l(m−l)−lis an inverse forx. Therefore,Ris a finite field.

(⇐): LetR be a finite field. Then that every elements inR will have an inverse. Let x ∈ R has its inverse. Letx 6= 0 ∈ Ras a nilpotent element. Then xⁿ = 0 for some n ∈ N. Since xhas an inverse, then we can say that xⁿ(x⁻¹)ⁿ⁻¹ = 0(x⁻¹)ⁿ⁻¹. This implies thatx = 0, which is a contradiction. Therefore,Rhas no non-zero nilpotent element. So,Rwill be a finite commutative ring with no non trivial idempotents.

3-2-1 Invariants of nil clean graphs

In this section, we study the properties of nil-clean graphs related to invariants of graph theory.

3-2-1-1 Girth of nil-clean graphs

In the following, we show the theorems that studied by Basnet (2017) that related to girth.

Theorem 3.2 The following hold true for nil clean graphGN(R)ofR:

(I) IfRis not a field, then girth ofG_N(R)is equal to3.

(II) IfRis a field, then

(a) girth is 2p ifR ∼= GF(p^k)(field of order p^k), where pis a odd prime and k > 1;

Chapter 3. Preliminary Results 14

(b) girth is infinite, in factG_N(R)is a path, otherwise.

Proof: For(I): fromLemma 3.2, we know that ifRis not a field, thenRwill not be a finite commutative reduced rings with no non trivial idempotents. This implies thatR will have at least one non trivial nilpotent or non trivial idempotent.

Case 1: If there exists a non trivial nilpotent, says,n∈R, then we have 1

0

n

Figure 8: Girth ofG_N(R)with non trivial nilpotent

So, the girth ofGN(R)is3.

Case 2: If there exists a non trivial idempotent, says,e∈R, then we have (1−e)

0

e

Figure 9: Girth ofG_N(R)with non trivial idempotent

So, the girth ofGN(R)is also3.

For(II): note that the set of nil clean elements of finite field is{0,1}, so, the nil clean graph forZ^p, wherepis prime, is shown as the following:

0 1 p−1 2 p−2 3 ^p+32

p−1 2

p+1 2

Figure 10: Nil clean graph ofZp

Chapter 3. Preliminary Results 15

From Figure 10, we can see that the girth ofG_N(Zp)is infinite. Hence, (b) holds true. From the characteristic of finite field that the nil clean graph ofGF(p^k)forp >2, we can clearly see that the graph will be disconnected. Furthermore, the disconnected graph will be consisting of a path of lengthp−1 and(^pk−1₂⁻¹)number of 2p cycles.

LetA⊆ GF(p^k)whereGF(p^k) = Zp[x]/hf(x)i, f(x)is a irreducible polynomial of degreekoverZp. Now,Awill consist all the linear combination ofx, x², ..., x^k−1 with coefficient of fromZp such thatg(x) +hf(x)i ∈Athen−g(x) +hf(x)i ∈/ A. Next, we can expressAasA={g_i(x) =g_i(x) +hf(x)i|1≤i≤(^pk−1₂⁻¹)}. So, we have

0 1 p−1 2 ^p−12

p+1 2

g₁(x) (−g₁(x) + 1)(g₁(x) +p−1)(−g₁(x) + 2) (−g₁(x) + ^p−1₂ )(g₁(x) + ^p+1₂ )

−g₁(x) (g₁(x) + 1)(−g₁(x) +p−1)(g₁(x) + 2) (g₁(x) + ^p−1₂ )(−g₁(x) + ^p+1₂ ) g2(x) (−g2(x) + 1)(g2(x) +p−1)(−g2(x) + 2) (−g₂(x) + ^p−1₂ )(g₂(x) + ^p+1₂ )

−g₂(x) (g₂(x) + 1)(−g₂(x) +p−1)(g₂(x) + 2) (g₂(x) + ^p−1₂ )(−g₂(x) + ^p+1₂ )

gpk−1−1 2

(x) A B C D E

−gpk−1−1 2

(x) A⁰ B⁰ C⁰ D⁰ E⁰

Figure 11: Nil clean graph ofGF(p^k) Here,A=−gpk−1−1

2

(x) + 1,B =gpk−1−1 2

(x) +p−1,C =−gpk−1−1 2

(x) + 2,

D=−gpk−1−1 2

(x) + ^p−1₂ ,E =gpk−1−1 2

(x) + ^p+1₂ , A⁰ =gpk−1−1

2

(x) + 1,B⁰ =−gpk−1−1 2

(x) +p−1,C⁰ =gpk−1−1 2

(x) + 2,

Chapter 3. Preliminary Results 16

D⁰ =gpk−1−1 2

(x) + ^p−1₂ ,E⁰ =−gpk−1−1 2

(x) + ^p+1₂ ,

From Figure 11, we can see that the girth will be 2p provided p is odd prime for R ∼=GF(p^k)

Theorem 3.3 G_N(R)is bipartite if and only ifRis a field.

Proof: (⇒): LetG_N(R)be bipartite, so girth ofG_N(R)will be a even number. Hence, byTheorem 3.2,Ris a field.

(⇐): ByTheorem 3.2, ifR is a field, thenR ∼= GF(p^k)andG_N(R)will have girth with even length. In fact,G_N(R)can be in a form of bipartite graph.

0

1

p−1

2 ^p−12

p+1 2

g₁(x)

(−g₁(x) + 1)

(g₁(x) +p−1)

(−g₁(x) + 2) (−g1(x) + ^p−1₂ )

(g₁(x) + ^p+1₂ )

−g₁(x)

(g₁(x) + 1)

(−g₁(x) +p−1)

(g₁(x) + 2) (g₁(x) + ^p−1₂ )

(−g1(x) + ^p+1₂ ) g₂(x)

(−g2(x) + 1)

(g₂(x) +p−1)

(−g2(x) + 2) (−g₂(x) + ^p−1₂ )

(g₂(x) + ^p+1₂ )

−g2(x)

(g₂(x) + 1)

(−g2(x) +p−1)

(g₂(x) + 2) (g₂(x) + ^p−1₂ )

(−g₂(x) + ^p+1₂ )

Figure 12: Bipartite nil clean graph ofGF(p^k)

From the definition of bipartite graph, let subsetV₁ ={0, p−1,^p+1₂ , g₁(x),(g₁(x)+

1), ...}and subsetV₂ ={1,2,^p−1₂ ,−g₁(x),(−g₁(x)+1), ...}and every edge inG_N(GF(p^k)) has the form e = (x, y) ∈ E(G_N(GF(p^k))), where x ∈ V₁ andy ∈ V₂. Moreover, there are no two vertices both inV₁ or both inV₂ are adjacent.

Chapter 3. Preliminary Results 17

3-2-1-2 Chromatic Index of nil-clean graph

In the following, we show the theorem that studied by Basnet (2017) that related to chromatic index.

Theorem 3.4 LetRbe a finite commutative ring then nil clean graph ofRis of class 1.

Proof: We colour the edge ab with the colour a +b. By this colouring, every 2 distinct edges ab and ac has different colour. Let C be the set of colours and let {x, x1, x2, x3, ..., xn} ⊆ Rsuch that{x+x1, x+x2, x+x3, ..., x+xn} ⊂ N C(R), we will have

x x₁

x₂

x₃ x_n

Figure 13: GN(R)withn+ 1elements

So, we have C = {x+x1, x+x2, x+x3, ..., x+xn}. Then,χ⁰(GN(R)) ≤ |C|

which indicates nil clean graph have |C|-edges colouring. Since C ⊂ N C(R), this indicates that |C| ≤ |N C(R)| and result in χ⁰(GN(R)) ≤ |C| ≤ |N C(R)|. By Lemma 3.1, we know that deg(x) ≤ |N C(R)| and deg(x) ≤ |N C(R)| − 1, then impliesdeg(x) ≤ deg(x) + 1 ≤ |N C(R)|. So, it is true for deg(x) = ∆ = |C| and

∆≤ |N C(R)|, thenχ⁰(G_N(R))≤∆. By Vizings theorem, we haveχ⁰(G_N(R))≥∆.

This will result inχ⁰(GN(R)) = ∆, soGN(R)is class1.

3-2-1-3 Diameter of nil clean graph

In the following, we show some results that studied by Basnet (2017) that related to diameter.

Lemma 3.3 Ris nil clean ring if and only ifdiam(G_N(R)) = 1.

Chapter 3. Preliminary Results 18

Proof: (⇒): LetR be a nil clean ring, then∀r ∈ R must be nil clean elements. We know thatr =n+ewheren ∈N il(R)ande∈Idem(R). So, we have

n e

Figure 14: Nil clean graph of elementsnande which give the result ofdiam(G_N(R)) = 1.

(⇐): Letdiam(G_N(R)) = 1, which indicates the maximum distances of each pair of distinct vertices inG_N(R)must be1. Let arbitraryx, y ∈Rand sincediam(G_N(R)) = 1, so r = x+ymust be nil clean element. So, ∀r ∈ R must be nil clean elements.

Therefore,Risnil clean ring.

Theorem 3.5 LetR be a non nil clean, weak nil clean ring with no non trivial idem- potents thendiam(G_N(R)) = 2.

Proof: At first, let R be a weak nil clean ring with no non trivial idempotents.

Then, we let arbitrarya, b∈Rand for somen₁, n₂ ∈ N il(R). We havea =n₁, n₁+ 1orn₁−1andb=n₂, n₂+ 1orn₂−1. We have the following table

n₁ n₁+ 1 n₁−1

n₂ (n₁) (n₂) (n₁+ 1) (n₂) (n₁−1) (1) (n₂) d(a, b) = 1 d(a, b) = 1 d(a, b) = 2 n₂+ 1 (n₁) (n₂ + 1) (n₁ + 1) (−1) (n₂+ 1) (n₁−1) (n₂+ 1)

d(a, b) = 1 d(a, b) = 2 d(a, b) = 1

n2−1 (n1) (1) (n2−1) (n1+ 1) (n2−1) (n1−1) (1) (n2 −1) d(a, b) = 2 d(a, b) = 1 d(a, b) = 2

Table 3: All combination ofd(a, b)

Thus, from Table 3 we can conclude thatdiam(G_N(R))≤2.

Now, letR be a non nil clean ring with no non trivial idempotents. Since non nil cleanindicatesn, n+ 1 ∈/ R, then we have at least onex ∈ Rsuch that x = n−1.

So,d(0, x)will be equal to2since (0) (1) (n−1), thereforediam(G_N(R))≥2.

Chapter 3. Preliminary Results 19

So, ifRisweak nil clean ring with no non trivial idempotents,diam(G_N(R))≤2 and ifRisnon nil clean ring with no non trivial idempotents, diam(G_N(R))≥2.

Hence, a non nil clean, weak nil clean ring with no non trivial idempotents will havediam(G_N(R)) = 2.

Theorem 3.6 LetR = A×B, such that Ais nil clean andB is weak nil clean with no non trivial idempotents, thendiam(G_N(R)) = 2.

Proof: SinceAhas non trivial idempotents, lete∈Idem(A), then we haveIdem(R) = {(e,0_B),(e,1_B)|e∈Idem(A)}. Now let(a₁, b₁),(a₂, b₂)∈R, if(a₁, b₁) + (a₂, b₂)is nil clean indicates that(a₁, b₁) (a₂, b₂), then d((a₁, b₁),(a₂, b₂)) = 1inG_N(R).

However, if(a₁, b₁) + (a₂, b₂)is not nil clean, it will be a result fromb₁+b₂ is not nil clean, becauseRis closed under addition. i.e Letn, n+e∈Awheren∈N il(A), e∈ Idem(A). So, now we havea₁ = n₁, n₁+e₁ anda₂ =n₂, n₂ +e₂. Clearly,a₁+a₂ must be nil clean.

SinceB is weak nil clean with no non trivial idempotents, letb₁ =n₁, n₁+ 1, n₁ −1 andb2 =n2, n2+ 1, n2−1, wheren1, n2 ∈N il(B). So, we have the following cases:

CASE I:Ifb₁ =n₁+ 1andb₂ =n₂+ 1, we have the path(a₁, b₁) (0,−1) (a₂, b₂) inGN(R), thusd((a1, b1),(a2, b2))≤2.

CASE II:Ifb₁ =n₁−1andb₂ =n₂−1, we have the path(a₁, b₁) (0,1) (a₂, b₂) inGN(R), thusd((a1, b1),(a2, b2))≤2.

CASE III:Ifb₁ =n₁−1andb₂ =n₂, we have the path(a₁, b₁) (0,1) (a₂, b₂)in G_N(R), thusd((a₁, b₁),(a₂, b₂))≤2.

CASE IV:Ifb₁ =n₁ andb₂ =n₂−1, we have the path(a₁, b₁) (0,1) (a₂, b₂)in G_N(R), thusd((a₁, b₁),(a₂, b₂))≤2.

Thereforediam(G_N(R)) ≤ 2, R is not nil clean implies diam(G_N(R)) ≥ 2. Thus, diam(G_N(R)) = 2

C ^HAPTER 4: g(x)- NIL CLEAN GRAPH

4-1 Introduction

LetRbe a ring and letg(x)be a polynomial inZ(R)[x], whereZ(R)denote as center of R. In L. Fan(2008), an element r ∈ R is called g(x)-nil clean ifr = n +s for somen∈N il(R)ands ∈Rsuch thatg(s) = 0. The ringRisg(x)-nil clean if every element inRisg(x)-nil clean.

Clearly, ifg(x) = x²−x, theng(x)-nil clean rings are nil clean. However, in gen- eral,g(x)-nil clean rings are not necessarily nil clean. We note this with the following example,

Example 2 Let Z(7) = {m/n | m, n ∈ Z, gcd(7, n) = 1} and letC₃ be the cyclic group of order3. By Wang and Chen (2004), the group ringZ⁽⁷⁾C₃ is(x⁶ −1)-clean.

However,Z(7)C₃ is not clean by Hans and Nicholson (2001).

Let g(x)-nil clean graph of ringR denote by G_N^?(R) and a set of g(x)-nil clean elements of ringRdenote byN^?(R). Letxandyto be distinct vertices of the elements fromg(x)-nil clean ringR, such thatxadjacent toyif and only ifx+y ∈N^?(R).

4-2 On x(x − 2)-nil clean graphs

In this section, we mainly focus on theg(x) = x²−2x∈Z(R)[x]. Hence, all theg(x) mentioned in the remaining of this chapter, theg(x)is defined byg(x) = x²−2x ∈ Z(R)[x]. Next, we will provide some examples onx(x−2)-nil clean graphs.

Example 3 We denoted thatGF(25)is a finite field with 25 elements. We show that theGF(25)is ax(x−2)-nil clean graph.

GF(25)∼=Z5[x]/hx²+x+ 1i

={ax+b+hx²+x+ 1i:a, b∈Z5}

Letβ =x+hx² +x+ 1i. ThenGF(25) ={0,1,2,3,4, β,2β,3β,4β,1 +β,2 +

20

Chapter 4. g(x)-nil clean graph 21

β,3 +β,4 +β,1 + 2β,2 + 2β,3 + 2β,4 + 2β,1 + 3β,2 + 3β,3 + 3β,4 + 3β,1 + 4β,2 + 4β,3 + 4β,4 + 4β}.

0 2 3 4 1

β 4β+ 2 β+ 3 4β+ 4 β+ 1

4β β+ 2 4β+ 3 β+ 4 4β+ 1

2β 3β+ 2 2β+ 3 3β+ 4 2β+ 1

3β 2β+ 2 3β+ 3 2β+ 4 3β+ 1

Figure 15: g(x)-nil clean graph ofGF(25)

Example 4 We denoted thatGF(27)is a finite field with 27 elements. We show that theGF(27)is ax(x−2)-nil clean graph.

GF(27) ∼=Z³[x]/hx³+ 2x² + 1i

={ax²+bx+c+hx³+ 2x²+ 1i:a, b, c∈Z³}

Letγ =x²+hx³+ 2x²+ 1iandδ =x+hx³+ 2x²+ 1i. ThenGF(27) ={0,1,2, δ, δ+ 1, δ+2,2δ,2δ+1,2δ+2, γ, γ+1, γ+2, γ+δ, γ+δ+1, γ+δ+2, γ+2δ, γ+2δ+1, γ+ 2δ+2,2γ,2γ+1,2γ+2,2γ+δ,2γ+δ+1,2γ+δ+2,2γ+2δ,2γ+2δ+1,2γ+2δ+2}

Chapter 4. g(x)-nil clean graph 22

0 2 1

δ 2δ+ 2 δ+ 1

2δ δ+ 2 2δ+ 1

γ 2γ+ 2 γ+ 1

2γ γ+ 2 2γ+ 1

γ+δ 2γ+ 2δ+ 2 γ+δ+ 1

2γ+ 2δ γ+δ+ 2 2γ+ 2δ+ 1

2γ+δ γ+ 2δ+ 2 2γ+δ+ 1

γ + 2δ 2γ+δ+ 2 γ+ 2δ+ 1 Figure 16: g(x)-nil clean graph ofGF(27)

Example 5 We denoted thatGF(49)is a finite field with 49 elements. We show that theGF(49)is ax(x−2)-nil clean graph.

GF(49)∼=Z7[x]/hx²+x+ 1i

={ax+b+hx²+x+ 1i:a, b∈Z7}

Letβ =x+hx²+x+ 1i. ThenGF(49) ={0,1,2,3,4,5,6, β,2β,3β,4β,5β,6β,1 + β,2+β,3+β,4+β,5+β,6+β,1+2β,2+2β,3+2β,4+2β,5+2β,6+2β,1+3β,2+

3β,3 + 3β,4 + 3β,5 + 3β,6 + 3β,1 + 4β,2 + 4β,3 + 4β,4 + 4β,5 + 4β,6 + 4β,1 + 5β,2 + 5β,3 + 5β,4 + 5β,5 + 5β,6 + 5β,1 + 6β,2 + 6β,3 + 6β,4 + 6β,5 + 6β,6 + 6β}

Chapter 4. g(x)-nil clean graph 23

0 2 5 4 3 6 1

β 6β+ 2 β+ 5 6β+ 4 β+ 3 6β+ 6 β+ 1

6β β+ 2 6β+ 5 β+ 4 6β+ 3 β+ 6 6β+ 1

2β 5β+ 2 2β+ 5 5β+ 4 2β+ 3 5β+ 6 2β+ 1

5β 2β+ 2 5β+ 5 2β+ 4 5β+ 3 2β+ 6 5β+ 1

3β 4β+ 2 3β+ 5 4β+ 4 3β+ 3 4β+ 6 3β+ 1

4β 3β+ 2 4β+ 5 3β+ 4 4β+ 3 3β+ 6 4β+ 1

Figure 17: g(x)-nil clean graph ofGF(49)

Next, we will investigate about thex(x−2)-nil clean graph fromZ3toZ34where Z^k ={0,1,2,3, . . . , k−1}for3≤k ≤34. The following illustration will be on the x(x−2)-nil clean graph form fromZ3 toZ34.

Chapter 4. g(x)-nil clean graph 24

Chapter 4. g(x)-nil clean graph 25

Chapter 4. g(x)-nil clean graph 26

Chapter 4. g(x)-nil clean graph 27

Figure 18: g(x)-nil clean graph ofZ³ toZ³⁴

Chapter 4. g(x)-nil clean graph 28

4-3 Some properties of g(x)-nil clean graph

In the following, we mainly study and investigate on some properties ofx(x−2)-nil clean graph. We first note the following for anyg(x)∈Z(R).

Theorem 4.1 Theg(x)-nil clean graphG_N^?(R)is a complete graph if and only ifR is ag(x)-nil clean ring.

Proof: (⇒): LetGN^?(R)be a completeg(x)-nil clean graph of ringR. Then it implies that for allr ∈ Rareg(x)-nil clean elements. Without lose of generality ofg(x)-nil clean elements, there exists a path fromrand it is connected to0, such thatr=r+ 0 which isg(x)-nil clean. HenceRisg(x)-nil clean.

(⇐): Conversely, let R be a g(x)-nil clean ring. To form a graph in R, we let anyq arbitrary elementsx, y ∈ R, x andyare connected if and only if x+yis a g(x)-nil clean element. So, this implies that every pairs of distinct elementr∈Rmust have a unique edges and it form the completeg(x)-nil clean graphG_N^?(R).

Lemma 4.1 LetG_N^?(R)be the g(x)-nil clean graph of a ring R. Then we have the following:

(I) If2xisg(x)-nil clean wherex∈R, thendeg(x) =|N^?(R)| −1.

(II) If2xis notg(x)-nil clean wherex∈R, thendeg(x) = |N^?(R)|.

Proof: Letx ∈ Rand clearlyx+R =R. Then for everyy ∈N^?(R), there exists a unique elementx_y ∈Rsuch thatx+x_y =y. Thus, we havedeg(x)≤ |N^?(R)|

For (I): Now, we let{x₁, x₂, x₃, ..., x} ⊆ R and {x₁ +x, x₂ +x, x₃ +x, ...,2x} ⊆ N^?(R). Since we are not considering any loops, we illustrate the graph in the follow- ing:

x x₁

x₂

x₃ x

Figure 19: g(x)-nil clean graph withxelements includingx

Chapter 4. g(x)-nil clean graph 29

By the definition ofN_{GN ?(R)}(x) = {y∈V(G_N^?(R))|yis adjacent tox}, we know that y = {1,2,3, ..., x}. We have deg(x) = |N_{GN ?(R)}(x)| = |N_{GN ?(R)}[x]| −1 =

|N^?(R)| −1.

For(II): Now, we let{x₁, x₂, x₃, ..., x_y, x} ⊆Rand{x₁+x, x₂+x, x₃+x, ..., x+x_y} ⊆ N^?(R)but2x /∈N^?(R). Since we are not considering any loops, we have

x x₁

x₂

x₃ x_y

x

Figure 20:g(x)-nil clean graph withxelements excludingx

From the definition of N_{GN ?(R)}(x) = {y ∈ V(G_N^?(R))|yis adjacent tox}, we know thaty ={x₁, x₂, x₃, ..., x_y}. We havedeg(x) =|N_{GN ?(R)}(x)|=|N^?(R)|.

4-3-1 Invariants of g(x)-nil clean graphs

In this section, we provide some properties ofg(x)-nil clean graphs related to invariants of graph theory.

4-3-1-1 Connected and disconnected graph ofg(x)-nil clean graph Proposition 4.1 For alln≥3, then the following hold forZn

(I) Ifn = 2k, for allk ≥ 2. ThenG_N^?(Zn)is a disconnected graph (in particular, it can be built up into 2 parts, one part fills by even integers and the other part is filled by odd integers).

(a) Letn = 2k, wherek =p^q, andpis an odd prime and for all integerq ≥1.

ThenG_N^?(Zn)is a disconnected path graph.

(II) Ifn = 2k+ 1, for allk ≥1, thenG_N^?(Zⁿ)is a connected graph.

(a) Letn=p^q, wherepis an odd prime and for all integerq≥1. ThenGN^?(Zⁿ) is a path graph.

Chapter 4. g(x)-nil clean graph 30

Proof: (I): It is obvious by taking Zn(n is even) as a example in Figure 18. Further- more, it built up into2parts which are the even integers part and odd integers part, it exists two path that can be illustrate in the Figure 21.

1 n−1 3 n−3 5 n−5 k−2 k+ 2 k

0 2 n−2 4 n−4 6 k+ 3 k−1 k+ 1

Figure 21: disconnected path graph forg(x)-nil clean graph ofZ2k

(I)(a): Let n = 2k, where k = p^q, and pis an odd prime and for all integer q ≥ 1.

ThenG_N^?(Zn)is a disconnected path graph and the illustration can refer to Figure 21.

(II): It is obvious by takingZn (nis odd) as a example in Figure 18. Furthermore, it exists a path that can be illustrate in the Figure 22.

0

2

n−2

4

n−4

6

3

n−1

1

Figure 22: path graph forg(x)-nil clean graph ofZ2k+1

(II)(a): In particular, ifn=p^q, wherepis an odd prime and for all integerq≥1. Then G_N^?(Zn)is a path graph and it can be illustrate in Figure 22.

4-3-1-2 Hamiltonian Path and Cycle ofg(x)-nil clean graph

In the following, we prove the theorem that related to the hamiltonian path and hamil- tonian cycle.

Theorem 4.2 Letn≥3, then the following hold forZn

(I) Ifn = 2k, for allk ≥2, thenG_N^?(Zn)consists no hamiltonian path (In partic- ular,G_N^?(Zn)is built by two distinct, symmetry connected graphs).

Chapter 4. g(x)-nil clean graph 31

(a) If we consider either one of the part ofG_N^?(Zn), then G_N^?(Zn)consists at least one hamiltonian path or hamiltonian cycle.

(II) Ifn = 2k+1, for allk ≥1, thenG_N^?(Zn)must consists at least one hamiltonian path.

Proof: (I): By Proposition 4.1, Ifn = 2k, for allk ≥ 2, G_N^?(Zn)is a disconnected graph. Therefore, it consists no hamiltonian path in the graph.

(a) We now consider one of the part of G_N^?(Zn) wheren = 2k andk = 2a, for all a≥2 (a∈Z). We can obtain a hamiltonian cycle inG_N^?(Z2k)and illustrate the cycle in the Figure 23.

0 2 n−2 4 n−4 6 k−2 k+ 2 k

1 n−1 3 n−3 5 n−5 k+ 3 k−1 k+ 1

Figure 23: hamiltonian cycle forg(x)-nil clean graph ofZ2kwherek = 2a For k = 2a+ 1, for all a ≥ 1 (a ∈ Z). We can obtain a hamiltonian path for GN^?(Z^2k)and refer the illustration in Figure 21.

(II): By Proposition 4.1, for n = 2k + 1, for all k ≥ 1, there exists at least one hamiltonian path in GN^?(Zⁿ) and illustration of hamiltonian path forGN^?(Zⁿ) is in Figure 22. Hence,G_N^?(Zn)is a connected graph.

This completes the proof. Furthermore, the illustration of hamiltonian paths and hamil- tonian cycles ofg(x)-nil clean graphs are presented inFigure 18. We note the hamil- tonian path or cycle with darker line.

4-3-1-3 Diameter ofg(x)-nil clean graph

In the following, we prove a theorem that related to the diameter.

Theorem 4.3 Letnbe a positive integer. Then the following holds forZn

Chapter 4. g(x)-nil clean graph 32

(I) Ifn = 2^k, for all integerk≥3k∈Z, thendiam(G_N^?(Zn)) =∞. In particular, if we consider either one of the part ofG_N^?(Zn), thendiam(G_N^?(Zn)) = 2^k−2− 1.

(II) Ifn=p^k, wherepis a odd prime, for allk≥1, thendiam(G_N^?(Zp^k)) =p^k−1.

(III) Ifn = 2p^k, wherepis a odd prime and for all integerk ≥1, thendiam(G_N^?(Z2p^k)) =

∞. However, if we consider either one of the part of the disconnected graph, then

diam(G_N^?(Z2p^k)) =p^k−1.

Proof: (I): By hypothesis, we haven = 2^k, for allk ≥ 3, thenGN^?(Zⁿ)is a discon- nected graph byProposition 4.1. Therefore,diam(G_N^?(Zn)) =∞. (I) follows from the graphGN^?(Zⁿ)in Figure24.

n 2

n

2 + 2 ⁿ₂ −2 ⁿ₂ + 4 ⁿ₂ −4 ⁿ₂ + 6 ³ⁿ₄ −2 ⁿ₄ + 2 ³ⁿ₄

0 2 n−2 4 n−4 6 ⁿ₄ −2 ³ⁿ

4 + 2 ⁿ₄

n

2 + 1 ⁿ₂ −1 ⁿ₂ + 3 ⁿ₂ −3 ⁿ₂ + 5 ⁿ₂ −5 ⁿ₄ + 3 ³ⁿ₄ −1 ⁿ₄ + 1

1 n−1 3 n−3 5 n−5 ³ⁿ

4 + 3 ⁿ₄ −1 ³ⁿ

4 + 1 Figure 24:g(x)-nil clean graph ofZⁿ

(II): ByProposition 4.1, for any integer,n =p^k, wherepis a odd prime, for allk≥1, then G_N^?(Zp^k) is a path graph. Therefore, (II) follows from the graph G_N^?(Zp^k) in Figure22.

(III) follows from the graphG_N^?(Z2p^k)in Figure25.

Chapter 4. g(x)-nil clean graph 33

0 2 2p^k−2 4 2p^k−4 6 p^k−3 p^k+ 3 p^k−1 p^k+ 1

1 2p^k−1 3 2p^k−3 5 2p^k−5 p^k+ 4 p^k−2 p^k+ 2 p^k

Figure 25: g(x)-nil clean graph ofZ2p^k

A matrix is said to be a shift matrix if a matrix with ones only on the superdiagonal or subdiagonal, and zeros elsewhere. For illustration, we let matrix U_n where the superdiagonal that containsn−1ones which is an upper shift matrix and matrixLn

where the subdiagonal that containsn−1ones which is a lower shift matrix, as follow 0 1

0 1 0 . ..

. .. 1 0 1

0 1 0























































 n−

1copies of1 U_n=

0 1 0

1 0 1 . ..

. .. 0 1 0

1 0























































 n−

1copies of1 L_n=

In this project, we define anti-shift matrix as a matrix with ones only on the anti- superdiagonal or anti-subdiagonal, and zeros elsewhere. For illustration, we let matrix U_n^? where the anti-superdiagonal that containsn−1ones which is an upper anti-shift matrix and matrixL^?_nwhere the anti-subdiagonal that contains n−1ones which is a lower anti-shift matrix, as follow

1 0 1 0 ... 0 1 ...

1 0 1 0 0























































 n−1copies

of1

U_n^? =

0 0 1 0 1 ... 1 0 ...

0 1 0 1





















































 n−1copies 

of1 L^?_n=

4-3-1-4 Adjacency Matrix ofg(x)-nil clean graph

Theorem 4.4 Letnbe a positive integer. Then the following holds forZⁿ

Chapter 4. g(x)-nil clean graph 34

(I) Ifn = 2^k, for all integer k ≥ 3,k ∈ Z, then G_N^?(Z2^k)follow the adjacency matrix ofM1(G_N^?(Z2^k)).

(II) If n = p^k, where p is a odd prime, for all k ≥ 1, then G_N^?(Zp) follow the adjacency matrix ofM2(G_N^?(Zp^k))which follows form of the sum of two anti- shift matrices.

(III) Ifn = 2p^k, where pis a odd prime and for all integer k ≥ 1, thenG_N^?(Z2p^k) follow the adjacency matrix ofM3(G_N^?(Z2p^k)).

Proof: (I): For illustration, we find the adjacency matrix of GN^?(Z2^k) where k = 3,4and5, which areM1(G_N^?(Z8)),M1(G_N^?(Z16))andM1(G_N^?(Z32))as follows

M1(G_N^?(Z8)) =



























0 0 1 0 1 0 1 0

0 0 0 1 0 1 0 1

1 0 0 0 1 0 1 0

0 1 0 0 0 1 0 1

1 0 1 0 0 0 1 0

0 1 0 1 0 0 0 1

1 0 1 0 1 0 0 0

0 1 0 1 0 1 0 0



























M1(G_N^?(Z16)) =





























































0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0



























































