Neighbouringhood distinguishing colourings of graphs
2020
Nafuka, Helena N
A thesis submitted in partial fulfilment of the requirements for the degree of Master of Science (Mathematics)
اظهر المزيد [+] اقل [-]In this mini thesis, we study neighbourhood distinguishing colouring (NDC) of graphs, which are proper colourings of the vertices with the added condition that for every pair u, v of distinct vertices there is some colour c such that the number of vertices of colour c adjacent to u is different to the number of vertices of colour c adjacent to v. The neighbourhood distinguishing colouring number XNDc( G) is defined as the minimum cardinality of a neighbourhood distinguishing colouring of a graph G. The study begins with the discussion of some terminologies and definitions used later on in our study. Moreover, we consider the colour classes corresponding to an NDC and the neighbourhood distinguishing colouring number of certain familiar classes of graphs such as paths, cycles and trees. In addition, we classify graphs with neighbourhood distinguishing colouring number XNDc( G) equal to two up to isomorphism. The chromatic number Xa of graphs G with XNDC equal to two is also two. Finally, we characterize graphs whose XNDC coincides with the order of the graph. These graphs possess a unique•XNDc- partition and they are either complete graphs or union of vertex disjoint edges. A XNDc-partition of a graph G is a partition of G with XNDC elements. The aim of this study is to give a considerable discussion of the neighbourhood distinguishing colouring and also to light the way for further research in the field of colourings.
اظهر المزيد [+] اقل [-]المعلومات البيبليوغرافية
تم تزويد هذا السجل من قبل University of Namibia