On the (upper) line-distinguishing and (upper) harmonious chromatic numbers of a graph

DSpace/Manakin Repository

Show simple item record

dc.contributor.advisor Prof. E. Jonck en
dc.contributor.author Immelman, Yolande
dc.date.accessioned 2009-03-31T09:26:03Z
dc.date.available 2009-03-31T09:26:03Z
dc.date.issued 2009-03-31T09:26:03Z
dc.date.submitted 2007-11
dc.identifier.uri http://hdl.handle.net/10210/2359
dc.description M.Sc. en
dc.description.abstract In this dissertation we study two types of colourings, namely line-distinguishing colourings and harmonious colourings. A line-distinguishing colouring of a graph G is a k-colouring of the vertices of G such that no two edges have the same colour. The line-distinguishing chromatic number G is defined as the smallest k such that G has a line-distinguishing k-colouring. A harmonious colouring of a graph G is a proper k-colouring of the vertices of G such that no two edges have the same colour, i.e. no two adjacent vertices can have the same colour. The harmonious chromatic number hG is defined as the smallest k such that G has a line-distinguishing k-colouring. In Chapter 0 we discuss some of the terminology and definitions used later on in our study. In Chapter 1 we introduce line-distinguishing colourings and consider the line-distinguishing chromatic number of certain familiar classes of graphs such as trees, paths, cycles and complete graphs. We also consider graphs with line-distinguishing chromatic number G equal to the usual chromatic number G, and we compare G with the chromatic index G of a graph. In Chapter 2 we mostly discuss minimal line-distinguishing (MLD) colourings. We consider minimal line-distinguishing colourings and graphs of diameter two as well as classes of regular MLD-colourable graphs. We also introduce the concept of distance regular graphs and discuss minimal line-distinguishing colourings in these graphs. In Chapter 3 we introduce a new parameter, namely the upper line-distinguishing chromatic number H G of a graph. We investigate H G for paths and cycles, and consider graphs with small upper line-distinguishing chromatic numbers. In Chapter 4 we consider the second type of colouring studied in this dissertation, namely harmonious colourings. We define the harmonious chromatic number hG and determine hG for certain classes of graphs such as paths, trees, cycles and complete graphs. In Chapter 5 we discuss upper and lower bound for hG. In Chapter 6 we discuss the upper harmonious chromatic number HG of a graph, and we determine HG for paths and cycles. We also consider graphs satisfying HG  G  1. The purpose of this study is to compile a resource which will give a thorough and well-integrated background on line-distinguishing and harmonious colourings. It is also intended to lay the groundwork for further doctoral studies in the field of colourings. en
dc.language.iso en en
dc.subject Graph coloring en
dc.title On the (upper) line-distinguishing and (upper) harmonious chromatic numbers of a graph en
dc.type Thesis en

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search UJDigispace


Advanced Search

Browse

My Account