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 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.

Grantor

Department of Mathematics and Applied Mathematics

Year dc:date.issued

2022

Author dc:creator

• Harnaker, Zahraa

Advisor dc:contributor.advisor

• Erwin, David

• Mathematics and Applied Mathematics

Handle dc:identifier.uri

http://hdl.handle.net/11427/37315

OAI identifier oai:identifier

oai:open.uct.ac.za:11427/37315