The domination subdivision number of a graph is the minimum number of edges that must be subdivided in order to increase the domination number of the graph. Likewise, the total domination subdivision number is the minimum number of edges that must be subdivided in order to increase the total domination number. First, this thesis provides a complete survey of established bounds on the domination subdivision number and the total domination subdivision number. Then in Chapter 4, new results regarding bounds on the total domination subdivision number are given. Finally, a characterization of the total domination subdivision number of caterpillars is presented in Chapter 5.

In a graph G=(V,E), a subset S ⊆ V is a double dominating set if every vertex in V is dominated at least twice. The minimum cardinality of a double dominating set of G is the double domination number. A graph G is double domination edge critical if for any edge uv ∈ E(G̅), the double domination number of G+uv is less than the double domination number of G. We investigate properties of double domination edge critical graphs. In particular, we characterize the double domination edge critical trees and cycles, graphs with double domination numbers of 3, and graphs with double domination numbers of 4 with maximum diameter.

L’histoire de la rencontre de l’Afrique et de l’Occident a, notamment, été énoncée en termes de « choc » ou d’« évènements-traumatismes ». Quoi qu’il en fût, c’est dans le cadre de la traite esclavagiste et de la colonisation que ces deux continents se sont « heurtés ». Leur confrontation a donc procédé, dans une large mesure, d’une pensée inégalitaire basée sur le postulat raciste, impulsée par une volonté répondant à des impératifs de conquête et économiques, supportée par un mode de gouvernement produisant et légitimant la domination et l’exploitation. Partant de l’évènement de cette rencontre et de son récit, il s’agit d’établir quels sont les concepts que la pensée imagine, façonne et énonce afin de justifier et d’exercer un pouvoir de domination. Énoncer, c’est fabriquer de la domination et la rendre légitime, telle est l’affirmation que nous étudions à travers le prisme de l’évènement de la rencontre – le temps de la colonie, particulièrement – et, également, après la colonie – en situation post-coloniale.Cette étude s’inscrit dans le questionnement critique post-colonial. À l’instar de la domination coloniale, il s’agit de déterminer, en Afrique post-coloniale, les imaginaires et les énoncés qui produisent et légitiment un pouvoir hégémonique, comment et par qui l’autorité s’exerce, ce qu’est le politique – tout est-il politique ? –, sur quels critères une pratique ou un discours constituent-t-ils des modalités d’expression et de participation politique ?En spécifiant l’énonciation de l’autorité – son « effet d’oracle » – et les stratégies de la domination coloniale et post-coloniale, la question de leur efficience et de leur omniscience se pose. L’enjeu est d’analyser la convergence des histoires afin de penser le post-colonial comme un engagement de la recherche dans la construction d’une démocratie post-raciale en Afrique et en Occident. / The history of the meeting of Africa and the Western world had, notably, been enunciated in terms of “clash” or “traumatic events”. Whatever has been done, it is in the framework of the slave business and of the colonialization that these two continents collided. Their confrontation came in large part from an unequal thinking based on the racist idea which comes from a willingness answering to obligations of conquest and economics, supported by a way of government producing and legitimizing domination and exploitation. Thus, from the event of this meeting and from its results, we must establish which are the concepts that the thought imagines, makes and enunciates to justify and exercise a power of domination. Enunciate, it is to create domination and make it legitimate, so strong is the affirmation that we study the event through a prism of this meeting, colonial times, particularly – and equally, after the colony – in a postcolonial situation.This study is written in the critical postcolonial questioning. In the links of the colonial domination, it is to determine, in postcolonial Africa, the imaginations and the enounced which produce and legitimize an hegemonic power, how and by who is the authority used, that which is policy – is everything policy? On which criteria does a practice or a speech constitute a way of expression and political participation?By specifying the enunciation of authority – his “oracle effect” – and the strategies of the colonial and postcolonial domination, the question of their success and of their omniscience must be asked. The challenge is to analyse the convergence of histories to the think of postcolonial as a commitment of research in the construction of a postracial democracy in Africa and in the West.

For a graph G = (V,E), we consider a bipartition {V1,V2} of the vertex set V by placing constraints on the vertices as follows. For every vertex v in Vi, we place a constraint on the number of neighbors v has in Vi and a constraint on the number of neighbors it has in V3-i. Using three values, namely 0 (no neighbors are allowed), 1 (at least one neighbor is required), and X (any number of neighbors are allowed) for each of the four constraints, results in 27 distinct types of bipartitions. The goal is to characterize graphs having each of these 27 types. We give characterizations for 21 out of the 27. Three other characterizations appear in the literature. The remaining three prove to be quite difficult. For these, we develop properties and give characterization of special families.

An Italian dominating function, abbreviated IDF, of $G$ is a function $f \colon V(G) \rightarrow \{0, 1, 2\}$ satisfying the condition that for every vertex $v \in V(G)$ with $f(v)=0$, we have $\sum_{u \in N(v)} f(u) \ge 2$. That is, either $v$ is adjacent to at least one vertex $u$ with $f(u) = 2$, or to at least two vertices $x$ and $y$ with $f(x) = f(y) = 1$. The Italian domination number, denoted $\gamma_I$(G), is the minimum weight of an IDF in $G$. In this thesis, we use operations that join two trees with a single edge in order to build trees with unique $\gamma_I$-functions.

For graphs G and H, a set S⊆V(G) is an H-forming set of G if for every v∈V(G)-S, there exists a subset R⊆S, where |R|=|V(H)|-1, such that the subgraph induced by R∪{v} contains H as a subgraph (not necessarily induced). The minimum cardinality of an H-forming set of G is the H-forming number γ {H}(G). The H-forming number of G is a generalization of the domination number γ(G) because γ(G)=γ {P2}(G) . We show that γ(G)γ {P3}(G)γ t(G), where γ t(G) is the total domination number of G. For a nontrivial tree T, we show that γ {P3}(T)=γ t(T). We also define independent P 3-forming sets, give complexity results for the independent P 3-forming problem, and characterize the trees having an independent P 3-forming set.

A subset S⊆V in a graph G=(V,E) is a [j,k]-set if, for every vertex vεV\-S, j≤|N(v)\∩S|≤k for non-negative integers j and k, that is, every vertex vεV\-S is adjacent to at least j but not more than k vertices in S. In this paper, we focus on small j and k, and relate the concept of [j,k]-sets to a host of other concepts in domination theory, including perfect domination, efficient domination, nearly perfect sets, 2-packings, and k-dependent sets. We also determine bounds on the cardinality of minimum [1, 2]-sets, and investigate extremal graphs achieving these bounds. This study has implications for restrained domination as well. Using a result for [1, 3]-sets, we show that, for any grid graph G, the restrained domination number is equal to the domination number of G.

For a graph G = (V, E), a subset S ⊆ V (G) is an equivalence dominating set if for every vertex v ∈ V (G) \ S, there exist two vertices u, w ∈ S such that the subgraph induced by {u, v, w} is a path. The equivalence domination number is the minimum cardinality of an equivalence dominating set of G, and the upper equivalence domination number is the maximum cardinality of a minimal equivalence dominating set of G. We explore relationships between total domination and equivalence domination. Then we determine the extremal graphs having large equivalence domination numbers.

A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some vertex in S. The total domination number γt(G) is the minimum cardinality of a total dominating set in G. The annihilation number a(G) is the largest integer k such that the sum of the first k terms of the non-decreasing degree sequence of G is at most the number of edges in G. In this paper, we investigate relationships between the annihilation number and the total domination number of a graph. Let T be a tree of order n<2. We show that γt(T)≤a(T)+1, and we characterize the extremal trees achieving equality in this bound.

A subset S⊆V in a graph G=(V,E) is a [j,k]-set if, for every vertex vεV\-S, j≤|N(v)\∩S|≤k for non-negative integers j and k, that is, every vertex vεV\-S is adjacent to at least j but not more than k vertices in S. In this paper, we focus on small j and k, and relate the concept of [j,k]-sets to a host of other concepts in domination theory, including perfect domination, efficient domination, nearly perfect sets, 2-packings, and k-dependent sets. We also determine bounds on the cardinality of minimum [1, 2]-sets, and investigate extremal graphs achieving these bounds. This study has implications for restrained domination as well. Using a result for [1, 3]-sets, we show that, for any grid graph G, the restrained domination number is equal to the domination number of G.