No description available.

The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known vertex covering and dominating set problems in graphs. We consider the graph theoretical representation of this problem as a variation of the dominating set problem and define a set S to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S (following a set of rules for power system monitoring). The minimum cardinality of a power dominating set of a graph G is the power domination number γP(G). We show that the power dominating set (PDS) problem is NP-complete even when restricted to bipartite graphs or chordal graphs. On the other hand, we give a linear algorithm to solve the PDS for trees. In addition, we investigate theoretical properties of γP(T) in trees T.

A self-complementary graph is a graph isomorphic to its complement. A set S of vertices in a graph G is a restrained dominating set if every vertex in V(G) \ S is adjacent to a vertex in S and to a vertex in V(G) \ S. The restrained domination number of a graph G is the minimum cardinality of a restrained dominating set of G. In this paper, we study restrained domination in self-complementary graphs. In particular, we characterize the self-complementary graphs having equal domination and restrained domination numbers.

For a graph G=(V,E), we consider placing a variable number of pebbles on the vertices of V. A pebbling move consists of deleting two pebbles from a vertex u∈V and placing one pebble on a vertex v adjacent to u. We seek an initial placement of a minimum total number of pebbles on the vertices in V, so that no vertex receives more than some positive integer t pebbles and for any given vertex v∈V, it is possible, by a sequence of pebbling moves, to move at least one pebble to v. We relate this minimum number of pebbles to several other well-studied parameters of a graph G, including the domination number, the optimal pebbling number, and the Roman domination number of G.

Fricke, Haynes, Hedetniemi, Hedetniemi, and Laskar introduced the following concept. For a graph G = (V,E), let rho denote a property of interest concerning sets of vertices. A vertex u is rho-good if u is contained in a {minimum, maximum} rho-set in G and rho-bad if u is not contained in a rho-set. Let g denote the number of rho-good vertices and b denote the number of rho-bad vertices. A graph G is called rho-excellent if every vertex in V is rho-good, rho-commendable if g > b > 0, rho-fair if g = b, and rho-poor if g < b. In this thesis the property of interest is total domination. The total domination number, gammat, is the cardinality of a smallest total dominating set in a graph. We investigate gammat-excellent, gammat-commendable, gammat-fair, and gammat-poor graphs.

Every graph G = (V, E) has a dominating set S ⊆ V(G) such that any vertex not in S is adjacent to a vertex in S. We define a paired-dominating set S to be a dominating set S = {v1, v2,..., v2t-1, v2t} where M = {v1v2, v3v4, ..., v2t-1v2t} is a perfect matching in 〈S〉, the subgraph induced by S. The domination number of a graph G is the smallest cardinality of any dominating set of G, and the paired-domination number is the smallest cardinality of any paired-dominating set. Determining the domination number for grid graphs is a well-known open problem in graph theory. Not surprisingly, determining the paired-domination number for grid graphs is also a difficult problem. In this thesis, we survey past research in domination, paired-domination and grid graphs to obtain background for our study of paired-domination in grid graphs. We determine the paired-domination number for grid graphs Gr,c where r ∈ {2,3}, for infinite dimensional grid graphs, and for the complement of a grid graph.

The well studied class of irredundant vertex sets of a graph has been previously shown to be a special case of (a) a “Private Neighbor Cube” of eight classes of vertex subsets and (b) a family of sixty four classes of “generalised irredundant sets.” The thesis makes various advances in the theory of irredundance. More specifically: (i) Nordhaus-Gaddum results for all the sixty-four classes of generalised irredundant sets are obtained. (ii) Sharp lower bounds involving order and maximum degree are attained for two specific classes in the Private Neighbor Cube. (iii) A new framework which includes both of the above generalisations and various concepts of domination, is proposed. / Graduate

Thesis (MSc)--University of Stellenbosch, 2007. / Bibliography. Also available via the Internet.

A partir de la Révolution Islamique (1979), sous l’effet de la domination idéologique et du projet d’"Islamisation" qu’elle portait, le système éducatif en Iran a voulu former un "homme nouveau". Cette thèse a traité les tentatives du système éducatif pendant les 34 dernières années pour établir et perpétuer la domination idéologique et puis, analysé les valeurs diffusées par le programme scolaire notamment à travers les manuels scolaires et l'école, valeurs qui définissent les caractéristiques de cet "homme attendu" par le système éducatif. Mais les résistances des élèves dans l'école et des jeunes dans la société montrent que le système éducatif n'est pas arrivé à former son "homme attendu". Une grande partie des résistances apparait là où les failles de l'idéologie dominante se présentent. De plus, former les individus de la société selon un modèle monotype dans la période où nul, où qu’il se situe, n'échappe aux effets et aux conséquences de la modernité est impossible. En ouvrant une fenêtre vers d’autres mondes, les media officieux, Internet, les chaines de satellite, les réseaux sociaux virtuels, les diasporas et les intellectuels ont joué un rôle important dans ces résistances. Mais au 21ème siècle, dans une société à structure socio-politique fermée et génératrice, parce que fermée, d’une société aliénante, la tentative de copie conforme du modèle imposé par l'idéologie dominante ne peut aboutir qu’à la dichotomie. Cette étude conclut que l'aliénation sous ses différents aspects apparait comme la conséquence d'un modèle monotype imposé aux élèves par l'idéologie dominante. Ainsi le système éducatif a participé à la reproduction de l'aliénation dans cette société aliénante. / Since the Islamic Revolution (1979), through ideological domination and Islamisation, the educational system in Iran was set out to form a "new man". This thesis studies the attempts of the educational system during the past 34 years to establish and perpetuate ideological domination, and then analyzes the values transmitted by the curriculum through textbooks and schooling and defines the characteristics of this "ideal man".However, the resistance of students in school and youth in society shows that the educational system has been unable to form its "ideal man". Much resistance appears where the vulnerabilities in the dominant ideology arise. In addition, forming individuals in a society using a monotype model has been impossible during this period. Since the model is subjected to all the consequences of modernity and globalization. The opening of a window into other worlds, unofficial media, the Internet, satellite television channels, virtual social networks, diasporas and intellectuals have all played an important role in this resistance.But in the 21st century, in a society with a closed socio-political structure and generating alienating circumstances, the attempt to copy the model imposed by the dominant ideology can only lead to dichotomy. This study concludes that alienation in its various aspects appears as the consequence of a monotype model imposed on students by the dominant ideology. Thus, the educational system has contributed in the reproduction of general alienation in this society.

Ph.D. / In this thesis, our primary objective is to investigate the effects that various graph modifications have on the total domination number of a graph. In Chapter 1, we introduce basic graph theory concepts and preliminary definitions. In Chapters 2 and 3, we investigate the graph modification of edge removal. In Chapter 2, we characterize graphs for which the removal of any arbitrary edge increases the total domination number. We also begin the investigation of graphs for which the removal of any arbitrary edge has no effect on the total domination number. In Chapter 3, we continue this investigation and determine the minimum number of edges required for these graphs. The contents of Chapters 2 and 3 have been published in Discrete Applied Mathematics [15] and [16]. In Chapter 4, we investigate the graph modification of edge addition. In particular, we focus our attention on graphs for which adding an edge between any pair of nonadjacent vertices has no effect on the total domination number. We characterize these graphs, determine a sharp upper bound on their total domination number and determine which combinations of order and total domination number are attainable. 10 11 We also study claw-free graphs which have this property. The contents of this chapter were published in Discrete Mathematics [20]. In Chapter 5, we investigate the graph modification of vertex removal. We characterize graphs for which the removal of any vertex changes the total domination number and find sharp upper and lower bounds on the total domination number of these graphs. We also characterize graphs for which the removal of an arbitrary vertex has no effect on the total domination number and we further show that they have no forbidden subgraphs. The contents of this chapter were published in Discrete Applied Mathematics [14]. In Chapters 6 and 7, we investigate the graph modification of edge lifting. In Chapter 6, we show that there are no trees for which every possible edge lift decreases the domination number, and we characterize trees for which every possible edge lift increases the domination number. The contents of Chapter 6 were published in the journal Quaestiones Mathematicae [17]. In Chapter 7, we show that there are no trees for which every possible edge lift decreases the total domination number and that there are no trees for which every possible edge lift leaves the total domination number unchanged. We characterize trees for which every possible edge lift increases the total domination number. At the time of the writing of this thesis, the contents of Chapter 7 have been published online in the Journal of Combinatorial Optimization [18] and will appear in print in a future issue.