Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Domination in graphs: Vizing's conjecture
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...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
Department of Mathematics and Applied Mathematics
2023
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613229996310528 |
|---|---|
| access_status_str | Open Access |
| author | Harnaker, Zahraa |
| author2 | Erwin, David |
| author_browse | Erwin, David Harnaker, Zahraa |
| author_facet | Erwin, David Harnaker, Zahraa |
| author_sort | Harnaker, Zahraa |
| collection | Thesis |
| description | 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. |
| format | Thesis |
| id | oai:open.uct.ac.za:11427/37315 |
| institution | University of Cape Town (South Africa) |
| language | eng |
| last_indexed | 2026-06-10T12:32:50.328Z |
| license_str | Not specified — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UCTD — University of Cape Town Open Access Repository |
| publishDate | 2023 |
| publishDateRange | 2023 |
| publishDateSort | 2023 |
| publisher | Department of Mathematics and Applied Mathematics |
| publisherStr | Department of Mathematics and Applied Mathematics |
| record_format | dspace |
| source_str | UCTD — University of Cape Town Open Access Repository |
| spelling | oai:open.uct.ac.za:11427/37315 Domination in graphs: Vizing's conjecture Harnaker, Zahraa Erwin, David Mathematics and Applied Mathematics 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. 2023-03-07T11:14:41Z 2023-03-07T11:14:41Z 2022 2023-02-20T12:54:49Z Master Thesis Masters MSc http://hdl.handle.net/11427/37315 eng application/pdf Department of Mathematics and Applied Mathematics Faculty of Science |
| spellingShingle | Mathematics and Applied Mathematics Harnaker, Zahraa Domination in graphs: Vizing's conjecture |
| thesis_degree_str | Master's |
| title | Domination in graphs: Vizing's conjecture |
| title_full | Domination in graphs: Vizing's conjecture |
| title_fullStr | Domination in graphs: Vizing's conjecture |
| title_full_unstemmed | Domination in graphs: Vizing's conjecture |
| title_short | Domination in graphs: Vizing's conjecture |
| title_sort | domination in graphs vizing s conjecture |
| topic | Mathematics and Applied Mathematics |
| url | http://hdl.handle.net/11427/37315 |
| work_keys_str_mv | AT harnakerzahraa dominationingraphsvizingsconjecture |