Please be patient while the object screen loads.

Sign In

GlobalView

Add to Quick Collection

Immelman, Yolande. On the (upper) line-distinguishing and (upper) harmonious chromatic numbers of a graph. 2009-03-31T09:26:03Z.

File | Description | Size | Format | ||
---|---|---|---|---|---|

CONTENT1 | PDF Document | 1 MB | Adobe Acrobat PDF | View Details | Download |

MODS | MODS Metadata | 4 KB | XML Document | View Details | Download |

Please use this identifier to cite or link to this item: http://hdl.handle.net/10210/2359

- Title
- On the (upper) line-distinguishing and (upper) harmonious chromatic numbers of a graph
- Creator
- Immelman, Yolande
- Contributor
- Prof. E. Jonck
- Subject
- Graph coloring
- Date
- 2009-03-31T09:26:03Z
- Description
- M.Sc.
- Description
- 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 hG 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 hG and determine hG for certain classes of graphs such as paths, trees, cycles and complete graphs. In Chapter 5 we discuss upper and lower bound for hG. In Chapter 6 we discuss the upper harmonious chromatic number HG of a graph, and we determine HG for paths and cycles. We also consider graphs satisfying HG 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.

- Relationships
- Show Relationship Browser for this Object
- collection(s)
- ETDs
- collection(s)
- 22
- Identifier
- uj:8248
- Identifier
- http://hdl.handle.net/10210/2359
- Type
- Thesis
- Full Text

162 Visitors
135 Hits
35 Downloads

Disclaimer |
Privacy |
Copyright |
Contact |
Back To Top