A set D of vertices in a graph G is a 2-dominating set of G if every vertex in V − D has at least two neighbors in D. The 2-domination number of a graph G, denoted by γ2(G), is the minimum cardinality of a 2- dominating set of G. In this thesis, we discuss the 2-domination number of a special family of trees, called caterpillars. A caterpillar is a graph denoted by Pk(x1, x2, ..., xk), where xi is the number of leaves attached to the ith vertex of the path Pk. First, we present the 2-domination number of some classes of caterpillars. Second, we consider several types of complete caterpillars. Finally, we consider classification of caterpillars with respect to their spine length and 2-domination number.

In this paper, we initiate the study of a variant of Roman dominating functions. For a graph G=(V,E), a Roman {2}-dominating function f:V→{0,1,2} has the property that for every vertex v∈V with f(v)=0, either v is adjacent to a vertex assigned 2 under f, or v is adjacent to least two vertices assigned 1 under f. The weight of a Roman {2}-dominating function is the sum Σv∈Vf(v), and the minimum weight of a Roman {2}-dominating function f is the Roman {2}-domination number. First, we present bounds relating the Roman {2}-domination number to some other domination parameters. In particular, we show that the Roman {2}-domination number is bounded above by the 2-rainbow domination number. Moreover, we prove that equality between these two parameters holds for trees and cactus graphs with no even cycles. Finally, we show that associated decision problem for Roman {2}-domination is NP-complete, even for bipartite graphs.

A perfect Italian dominating function on a graph G is a function f:V(G)→{0,1,2} satisfying the condition that for every vertex u with f(u)=0, the total weight of f assigned to the neighbors of u is exactly two. The weight of a perfect Italian dominating function is the sum of the weights of the vertices. The perfect Italian domination number of G, denoted γ Ip (G), is the minimum weight of a perfect Italian dominating function of G. We show that if G is a tree on n≥3 vertices, then γ Ip (G)≤[Formula presented]n, and for each positive integer n≡0(mod5) there exists a tree of order n for which equality holds in the bound.

We mainly study two related dominating functions, namely, the weak Roman and 2-rainbow dominating functions. We show that for all graphs, the weak Roman domination number is bounded above by the 2-rainbow domination number. We present bounds on the weak Roman domination number and the secure domination number in terms of the total domination number for specific families of graphs, and we show that the 2-rainbow domination number is bounded below by the total domination number for trees and for a subfamily of cactus graphs.

An Italian dominating function on a graph G with vertex set V(G) is a function f: V(G) → { 0 , 1 , 2 } having the property that for every vertex v with f(v) = 0 , at least two neighbors of v are assigned 1 under f or at least one neighbor of v is assigned 2 under f. The weight of an Italian dominating function f is the sum of the values assigned to all the vertices under f. The Italian domination number of G, denoted by γI(G) , is the minimum weight of an Italian dominating of G. It is known that if G is a connected graph of order n≥ 3 , then γI(G)≤34n. Further, if G has minimum degree at least 2, then γI(G)≤23n. In this paper, we characterize the connected graphs achieving equality in these bounds. In addition, we prove Nordhaus–Gaddum inequalities for the Italian domination number.

Let $G$ be any graph and let $\overline{G}$ be its complement. The complementary prism of $G$ is formed from the disjoint union of a graph $G$ and its complement $\overline{G}$ by adding the edges of a perfect matching between the corresponding vertices of $G$ and $\overline{G}$. An Italian dominating function on a graph $G$ is a function such that $f \, : \, V \to \{ 0,1,2 \}$ and for each vertex $v \in V$ for which $f(v)=0$, it holds that $\sum_{u \in N(v)} f(u) \geq 2$. The weight of an Italian dominating function is the value $f(V)=\sum_{u \in V(G)}f(u)$. The minimum weight of all such functions on $G$ is called the Italian domination number. In this thesis we will study Italian domination in complementary prisms. First we will present an error found in one of the references. Then we will define the small values of the Italian domination in complementary prisms, find the value of the Italian domination number in specific families of graphs complementary prisms, and conclude with future problems.

The distance d(u, v) between two vertices u and v in a graph G equals the length of a shortest path from u to v. A set S of vertices is called a distance-2 dominating set if every vertex in V \S is within distance-2 of at least one vertex in S. The distance-2 domatic number is the maximum number of sets in a partition of the vertices of G into distance-2 dominating sets. We give bounds on the distance-2 domatic number of a graph and determine the distance-2 domatic number of selected classes of graphs.

La théorie des graphes est considérée comme un vaste champ qui permet d'explorer différentes techniques de preuve des mathématiques discrètes. Ainsi, les différents problèmes traités dans cette théorie ont plein d'applications dans d'autres domaines scientifiques tels que l'informatique, la physique, la sociologie, la théorie des jeux, etc. Dans cette optique, nous proposons, dans cette thèse, de mettre l'accent sur trois problèmes de graphes, à savoir la multidécomposition de multigraphes, la [1, 2]-domination et le monitoring des arêtes. Ainsi, le fait d'explorer, dans ce travail de thèse, trois problèmes de graphes relativement distincts dans des classes de graphes différentes, nous a permis de développer plusieurs techniques de preuve ainsi qu'une multitude de façon d'aborder un problème. La première partie de cette thèse touche un aspect très important de la théorie des graphes, appelé la décomposition des graphes. Intuitivement, une décomposition en sous-graphe permet de représenter le graphe d'origine par un ensemble de copies du sous-graphe, où chaque arête du graphe initial appartient à une et une seule copie du sous-graphe. Dans cette partie, on s'intéresse plus particulièrement à la décomposition multiple d'un multigraphe complet en étoiles et cycles de même taille, c.à.d. générer à partir d'un multigraphe, plusieurs composantes disjointes (étoiles et cycles). Dans ce sens, des preuves formelles sont présentées pour déterminer les conditions nécessaires et suffisantes que doit avoir le multigraphe complet pour qu'une telle décomposition existe. Les deux autres parties de cette thèse, les parties les plus consistantes, abordent un problème suscitant beaucoup d'attention actuellement, qui est l'étude de la domination dans les graphes. Le problème original de domination consiste à trouver un ensemble de sommets (de taille minimum) dominant le reste des sommets d'un graphe. De nombreuses variantes d'intérêts à la fois théoriques et pratiques ont été proposées et étudiées dans la littérature. Dans cette partie de thèse et celle qui suit, nous nous sommes intéressés à deux variantes de domination. La première variante, appelée [i, j]-domination dans les graphes, a été introduite par Chellali et al. en 2013. En plus de ses propriétés de domination, la particularité de cette variante est que chaque sommet non dominant doit être adjacent à au moins i et au plus j sommets dominants. Plus particulièrement, nous nous somme intéresses à la [1, 2]-domination. Il convient de souligner qu'il a été démontré que le problème reste NP-complet. Dans ce sens, nous avons étudié ce paramètre dans des graphes particuliers, tels que les graphes de Petersen généralisés, ce qui rend ce problème tout aussi intéressant. Introduite par Watkins, cette famille de graphes possède un nombre de propriétés très intéressantes. D'ailleurs, plusieurs paramètres de graphes ont été étudiés sur cette classe de graphes de par sa structure qui est assez particulière. De plus, une étude de la [1, 2]-total domination sur cette classe de graphes est aussi menée dans cette thèse. La deuxième et dernière variante étudiée, aussi une variante de la domination, appelée monitoring des arêtes, a été introduite par Dong et al. en 2008. Elle consiste à trouver un ensemble de sommets qui surveille (domine) l'ensemble des arêtes dans un graphe sachant qu'un sommet surveille une arête s'il forme un triangle avec les deux extrémités de l'arête. Une arête peut être monitorée par un ou plusieurs sommets. Dans ce contexte, plusieurs variantes du monitoring des arêtes sont considérées dans cette partie à savoir monitoring des arêtes, monitoring uniforme des arêtes et monitoring pondéré des arêtes. L'essence de ce problème réside dans sa nature combinatoire ainsi que son domaine d'application, plus particulièrement dans les réseaux de capteurs sans fil. De plus, il a été prouvé que trouver un ensemble minimum pour ce problème est NP-difficile [etc....] / Graph theory is considered as a field exploring a large variety of proof techniques in discrete mathematics. Thus, the various problems treated in this theory have applications in a lot of other scientific fields such as computer science, physics, sociology, game theory, etc. In this thesis, three major problems are considered: the multidecomposition of multigraphs, the [1, 2]- domination and the edge monitoring. The fact that these three problems are of different nature allowed us to explore several proof techniques in this thesis. The first part of this thesis deals with a popular aspect of research in graph theory called graph decomposition. Intuitively, a decomposition into subgraphs allows us to describe the original graph with a set of copies of these subgraphs. In this part, we give a particular interest to the multidecomposition of a complete multigraph into edge disjoint stars and cycles. Thus, we investigate the problem of (Sk, Ck)-multidecomposition of the complete multigraph and give necessary and sufficient conditions for such a multidecomposition to exist. The second and third parts are the most important parts in terms of effort and spent time. They are devoted to problems related to domination in graphs. The original domination problem is to find a minimum set of vertices such that every vertex outside the dominating set is adjacent to at least one vertex from the dominating set. Many variants of theoretical and practical interest have been studied in the literature. The second studied problem is called the [i, j]-domination in graphs. This problem was introduced by Chellali et al. in 2013. In addition to the properties of domination, this variant has the particularity that each non-dominating vertex should be adjacent to at least i dominating vertices but also to at most j of them. We particularly focus on the [1, 2]-domination. It has been shown that the problem remains NP-complete. We are interested to study this problem on a particular graph namely the generalized Petersen graph. This graph was introduced by Watkins and has a lot of interesting properties. Moreover, several graph theoretical parameters have been studied on this graph class because of it unique structure. In addition, a study of the [1, 2]-total domination is also proposed at the end of this part. The last problem is a new variant called edge monitoring problem and was introduced by Dong et al. in 2008. It consists to find a set of vertices that monitors (dominates) the edge set of a graph such as a vertex monitors an edge if it forms a triangle with it i.e. it dominates both extremities of the edge. An edge can be monitored by one or more vertices. Three variants of the problem are considered in this part namely the edge monitoring, uniform edge monitoring and weighted edge monitoring. The essence of this problem lies on its combinatorial aspect and its range of applications in networks; especially wireless sensor networks. This problem is known to be NP-hard. Given the complexity of this kind of problems, we are first interested by a theoretical study: variants of the problem, bounds, characterizations, etc. We give more in depth studies of the problem for several graph classes