Packings and coverings in graphs

(Manuscript [Fr])

In this thesis, we tell about packings and coverings in graphs. The problem of packings has been largely studied in the context of error correcting codes, while the problem of coverings is related to domination, one of the main graph theory problems.


Chapter 1 is dedicated to definitions. In chapter 2, we study two generalizations of problems of codes. The first is a common generalization of perfect Hamming codes and perfect Lee codes. These metrics may be defined as the product of complete graphs and of cycles, respectively. We prove existence as well as nonexistence results of perfect codes on the mixed product of K2 and infinite cycles, that were published in a paper entitled Perfect codes in Cartesian product of 2-paths and infinite paths.

Then, we study a weighted version of perfect codes, namely perfect weighted coverings of radius one. We present them as (a,b)-codes, and we study them in the Lee metric. We again present results of existence and of nonexistence, which have since bee improved and published in wighted-codes in Lee metric.


With chapter 3, we make a transition between codes and domination by reminding the duality. This property allows us to characterize the total domination number and the open packing number of the Cartesian product of two paths of same length. The proof uses only constructions, and is now published in a paper entitled On open packings and total coverings of two-dimensional grid graphs.


Then, we study variations of domination in graphs. In chapter 4, we study domination on graph products. This work takes part in the research related to Vizing's conjecture. We first give new bounds on the total domination number of the direct product of graphs, depending on other parameters of domination. These bounds are published in a paper entitled Some results on total domination in direct products of graphs.

An iterated domination variation has been recently proposed, called power domination. Widely completing the recent work started by Dorfling and Henning on the Cartesian product of paths, we specify the minimum power domination number of the other products of paths. This works is accepted for publication in a paper entitled Power domination in product graphs.

Finally, we prove a Vizing like relation for upper total domination, showing that the upper total domination number of the Cartesian product of two graphs is at least twice the product of the upper total domination number of its factors. A lemma we use also permits us to infer that the upper total domination number of a graph is at most twice its upper domination number. These results are to appear in a paper called On the upper total domination number of Cartesian products of graphs.


In chapter 5, we study domination with a more structural point of view, related to graph classes. We begin with paired-domination, for which Favaron and Henning proved some bound for the class of claw-free cubic graphs. We extend their results to the families of star-free graphs, giving a sharp bound for each size of stars. This result is published in a paper called Paired-domination in generalized claw-free graphs. Haynes and Slater characterized the graphs for which minimum paired-dominating sets contain all the vertices except one. They are mainly subdivided stars. Therefore, we naturally studied paired-domination in P5-free graphs, P5 being one of the smallest subdivided stars. We found a new bound, and we were able to give an infinite family of graphs reaching this bound. These results are submitted in a paper entitled Paired-domination in P5-free graphs.

Upper domination problems have also drawn quite some attention recently. Since a very large number of variations on domination are now studied by the community, it seems important to build links between them. It is in this prospect that we studied links between upper total and upper paired-domination, especially in the case of trees. The results presented have been published in a paper called Upper total domination versus upper paired-domination.