Domination in graphs: Vizing's conjecture
| dc.contributor.advisor | Erwin, David | |
| dc.contributor.author | Harnaker, Zahraa | |
| dc.date.accessioned | 2023-03-07T11:14:41Z | |
| dc.date.available | 2023-03-07T11:14:41Z | |
| dc.date.issued | 2022 | |
| dc.date.updated | 2023-02-20T12:54:49Z | |
| dc.description.abstract | Vizing's conjecture remains one of the biggest open problems in domination in graph theory today. The conjecture states that the domination number of the Cartesian product of two graphs is at least as large as the product of the domination numbers of the two factor graphs. The aim of this thesis is to study the various approaches implemented by researchers over the years in an attempt to prove (or disprove) Vizing's conjecture. Graph-theoretic definitions and notations used in this paper are presented in Chapter 1, along with several theorems on domination that will be useful throughout this paper. In Chapters 2, 3 and 4, we explore some of the earliest research done in solving Vizing's conjecture. The three methods studied, namely the simple-labelling rule, the one-half argument and fair reception, all involve partitioning the vertex set of one of the factor graphs in some way and then utilising the structure of the Cartesian product to characterise large classes of graphs for which the conjecture is true. Since Vizing's conjecture is unsolved in general, many partial results related to the conjecture have been proven over the years. One such result, the use of which has become quite widespread in the literature, is studied in Chapter 5. This partial result states that the domination number of the Cartesian product of two graphs is at least half the product of the domination numbers of the two factor graphs. We analyse the double projection argument used to prove this result and include more recent improvements of this bound. We then consider other approaches to solving Vizing's conjecture which do not use some vertex-partitioning technique. Chapter 6 deals with proving the conjecture by minimal counterexample and we list a few properties that a possible minimal counterexample to Vizing's conjecture must satisfy. Moreover, we focus on methods of building graphs which satisfy Vizing's conjecture from other graphs in Chapter 7. Finally, Chapter 8 covers several variations of domination and Vizing-like results for each type of domination. In particular, notable results in fractional, graph-, total, integer, paired-, upper and rainbow domination are studied in detail. | |
| dc.identifier.apacitation | Harnaker, Z. (2022). <i>Domination in graphs: Vizing's conjecture</i>. (). ,Faculty of Science ,Department of Mathematics and Applied Mathematics. Retrieved from http://hdl.handle.net/11427/37315 | en_ZA |
| dc.identifier.chicagocitation | Harnaker, Zahraa. <i>"Domination in graphs: Vizing's conjecture."</i> ., ,Faculty of Science ,Department of Mathematics and Applied Mathematics, 2022. http://hdl.handle.net/11427/37315 | en_ZA |
| dc.identifier.citation | Harnaker, Z. 2022. Domination in graphs: Vizing's conjecture. . ,Faculty of Science ,Department of Mathematics and Applied Mathematics. http://hdl.handle.net/11427/37315 | en_ZA |
| dc.identifier.ris | TY - Master Thesis AU - Harnaker, Zahraa AB - Vizing's conjecture remains one of the biggest open problems in domination in graph theory today. The conjecture states that the domination number of the Cartesian product of two graphs is at least as large as the product of the domination numbers of the two factor graphs. The aim of this thesis is to study the various approaches implemented by researchers over the years in an attempt to prove (or disprove) Vizing's conjecture. Graph-theoretic definitions and notations used in this paper are presented in Chapter 1, along with several theorems on domination that will be useful throughout this paper. In Chapters 2, 3 and 4, we explore some of the earliest research done in solving Vizing's conjecture. The three methods studied, namely the simple-labelling rule, the one-half argument and fair reception, all involve partitioning the vertex set of one of the factor graphs in some way and then utilising the structure of the Cartesian product to characterise large classes of graphs for which the conjecture is true. Since Vizing's conjecture is unsolved in general, many partial results related to the conjecture have been proven over the years. One such result, the use of which has become quite widespread in the literature, is studied in Chapter 5. This partial result states that the domination number of the Cartesian product of two graphs is at least half the product of the domination numbers of the two factor graphs. We analyse the double projection argument used to prove this result and include more recent improvements of this bound. We then consider other approaches to solving Vizing's conjecture which do not use some vertex-partitioning technique. Chapter 6 deals with proving the conjecture by minimal counterexample and we list a few properties that a possible minimal counterexample to Vizing's conjecture must satisfy. Moreover, we focus on methods of building graphs which satisfy Vizing's conjecture from other graphs in Chapter 7. Finally, Chapter 8 covers several variations of domination and Vizing-like results for each type of domination. In particular, notable results in fractional, graph-, total, integer, paired-, upper and rainbow domination are studied in detail. DA - 2022_ DB - OpenUCT DP - University of Cape Town KW - Mathematics and Applied Mathematics LK - https://open.uct.ac.za PY - 2022 T1 - Domination in graphs: Vizing's conjecture TI - Domination in graphs: Vizing's conjecture UR - http://hdl.handle.net/11427/37315 ER - | en_ZA |
| dc.identifier.uri | http://hdl.handle.net/11427/37315 | |
| dc.identifier.vancouvercitation | Harnaker Z. Domination in graphs: Vizing's conjecture. []. ,Faculty of Science ,Department of Mathematics and Applied Mathematics, 2022 [cited yyyy month dd]. Available from: http://hdl.handle.net/11427/37315 | en_ZA |
| dc.language.rfc3066 | eng | |
| dc.publisher.department | Department of Mathematics and Applied Mathematics | |
| dc.publisher.faculty | Faculty of Science | |
| dc.subject | Mathematics and Applied Mathematics | |
| dc.title | Domination in graphs: Vizing's conjecture | |
| dc.type | Master Thesis | |
| dc.type.qualificationlevel | Masters | |
| dc.type.qualificationlevel | MSc |