Abd Karim, Nor Suriya (2007) Chromaticity Of K4Homeomorphs With Girth 9 And 6Bridge Graphs. Doctoral thesis, Universiti Pendidikan Sultan Idris.

Text
CHROMATICITY OF K4_HOMEOMORPHS WITH GIRTH 9 AND 6_BRIDGE GRAPHS.pdf Download (1MB)  Preview 
Abstract
The chromaticity of graphs is the term used referring to the question of chromatic equivalence and chromatic uniqueness of graphs. Since the arousal of the interest on the chromatically equivalent and chromatically unique graphs, various concepts and results under the said areas of research have been discovered and many families of such graphs have been obtained. The purpose of this thesis is to contribute new results on the chromaticity of graphs, specifically, K4  homeomorphs with girth 9 and 6bridge graphs. A K4  homeomorph is a graph derived from a complete graph, K4. Such a homeomorph is denoted by K4(a, b, c, d, e, f) where the six edges of K4 are replaced by the six paths of length a, b, c, d, e and f. Let N and Ok be a set of natural numbers and a multigraph with two vertices and k edges, respectively. For any aI, a2, ... , ak E N, the graph O(al' a2, ... , ak) is a subdivision ofOk where the edged of Ok are replaced by paths of length a1,a2,...,ak,respectively. The subdivision of Ok is called a multibridge graph or a kbridge graph. The results in this thesis cover two main parts. The first part involves the chromaticity of K4  homeomorphs with girth 9 and the second part discusses the chromaticity of 6bridge graphs. We first study the chromaticity of a type of K4homeomorphs with girth 9, that is, the graph K4(2,3,4,d,e,f). We then investigate the chromaticity of another type of K4homeomorphs with girth 9, that is, the graph K4(,4,4,d,e,f). Then, we obtain the complete solution for the chromaticity of all types of K4 homeomorphs with girth 9. For the latter part, we first investigate the chromaticity of 6bridge graph O(3,3,3,b,b,c) where 3< b < c. We next study the chromaticity of 6 bridge graph O(a,a,a,b,b,c) where 2 < a < b < c. We continue to determine the chromaticity of 6bridge graph O(a,a,b,b,b,c) where 2<a<b<c. Next, we investigate two more types of 6bridge graphs of the form O(3,3,b,b,c,c) where 3<b<c and O(3,3,3,b,c,d) where 3<b<c<d. Many new results on the chromaticity of K4homeomorphs with girth 9 and 6bridge graphs are obtained. We end this thesis by including some open problems for further investigation.
Item Type:  Thesis (Doctoral) 

Subjects:  Q Science > QA Mathematics 
Faculties:  Faculty of Science and Mathematics 
Depositing User:  Muhamad Awais Mahadzir 
Date Deposited:  24 May 2018 08:19 
Last Modified:  24 May 2018 08:19 
URI:  http://ir.upsi.edu.my/id/eprint/828 
Actions (login required)
View Item 