Dissertations / Theses on the topic 'Roman domination'

In this thesis, we introduce Roman domination cover rubbling as an extension of domination cover rubbling. We define a parameter on a graph $G$ called the \textit{Roman domination cover rubbling number}, denoted $\rho_{R}(G)$, as the smallest number of pebbles, so that from any initial configuration of those pebbles on $G$, it is possible to obtain a configuration which is Roman dominating after some sequence of pebbling and rubbling moves. We begin by characterizing graphs $G$ having small $\rho_{R}(G)$ value. Among other things, we also obtain the Roman domination cover rubbling number for paths and give an upper bound for the Roman domination cover rubbling number of a tree.

The complementary prism GG of a graph G is formed from the disjoint union of G and its complement G by adding the edges of a perfect match- ing between the corresponding vertices of G and G. A Roman dominating function on a graph G = (V,E) is a labeling f : V(G) → {0,1,2} such that every vertex with label 0 is adjacent to a vertex with label 2. The Roman domination number γR(G) of G is the minimum f(V ) = Σv∈V f(v) over all such functions of G. We study the Roman domination number of complementary prisms. Our main results show that γR(GG) takes on a limited number of values in terms of the domination number of GG and the Roman domination numbers of G and G.

Domination is a rapidly developing area of research in graph theory. This dissertation focuses on the Roman Domination Problem; it was introduced quite recently and has some interesting applications in real world problems such military strategies and wireless networking. Given a graph, a Roman Dominating Function is a function that labels the vertices of the graph with an integer between 0, 1, 2, satisfying the condition that every vertex labeled by 0 is adjacent to at least one vertex labeled by 2. The weight of a Roman Dominating Function is the sum of all the labels, and the minimum weight is called the Roman Domination Number. The Roman Domination Problem is to find such number and function. In this dissertation we study the Roman Domination Problem when restricted to the class of grid graphs, i.e. graphs that, when drawn on an Euclidean Plane, form a specific regular tiling. A review of well--known results is given, and new results are presented. We aimed to find an algorithm that can find an exact solution for all the grid graphs, and, to do so, we present some important results: we prove a better lower-bound and present an upper-bound on the Roman Domination Number which improves the previous one and, we conjecture, is the Roman Domination Number for many, if not all, grid graphs.

The effects of Romanization were believed to be devastating to the cultures conquered by Rome, but Britain was an exception. The Romanization of Britain began through trade with the continent long before the invasion by Claudius. But the natives of Britain did not accept the Roman culture as completely as other conquests by Rome. R. G. Collingwood did not believe that the Romans dominated the Celtic culture. What he observed in the inscriptions and archaeology of Britain was a conflation of both cultures. Roman Britain was a unique combination of Celtic and Roman culture that was achieved through mutual acceptance and practice of both cultures’ values. The examination of two of those values, religious and mortuary practices, can help reveal the extent of Romanization in Britain and finally confirm Collingwood’s theory of Romanization.

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.

L'objectif de cette thèse est d'étudier sur le long terme, depuis la fin de l'époque achéménide jusqu'à celle du Haut-Empire (aux alentours de 235 après J.-C.) l'implantation de troupes et de vétérans perses, gréco-macédoniens, thraces, lyciens et romains, puis de leurs descendants, dans l'espace phrygien, région quelque peu marginale située dans le centre-ouest de l'Anatolie. Après avoir dans la première partie identifié et justifié stratégiquement les différents lieux d'installation, elle examine l'impact économique de celle-ci au travers de l'étude de la mainmise sur la terre et ses productions, du rôle des soldats en tant que producteurs et consommateurs et de leur implication dans la sécurisation du territoire. Sur un plan social, le quotidien des militaires, des vétérans et de leurs familles est ensuite examiné, de même que les formes prises par leur domination sur le reste de la population et leurs choix religieux. Le tout s'appuie sur un vaste corpus de plusieurs centaines d'inscriptions et de monnaies
The objective of this thesis is to study on the long term, since the end of the achaemenid period until that of the roman Top-empire (near 235 AD) the setting-up of persian, greco-macedonian, thracian, lycian and roman troops and veterans, then of their descendants, in the Phrygian space, a little marginal region situated in west central Anatolia. Having in the first part identified and justified strategically the various places of installation, it examines the economic impact of this one through the study of the seizure by the earth and its productions, the role of the soldiers as producers and consumers and of their implication in the reassurance of the territory. On a social plan, the everyday life of the servicemen, the veterans and their families is then examined, as well as the forms taken by their domination on the rest of the population and their religious choices. The whole is based on a vast corpus of several hundred inscriptions and coins

Una funzione di Dominazione Romana su un grafo G è una funzione di copertura che assegna ai vertici del grafo uno tra i valori (0, 1, 2) con l'unico vincolo che ogni vertice con valore 0 abbia almeno un vicino con valore 2. Il peso di una funzione di Dominazione Romana è la somma di tutti i valori assegnati e il numero di Dominazione Romana di un grafo G è definito come il minimo tra tutte le funzioni di Dominazione Romana su G. Dopo un'introduzione ai concetti base che ruotano attorno alla Dominazione Romana, viene studiato il problema per due particolari classe di grafi, cioè grafi a griglia e i bipartiti. Per i grafi a griglia vengono prodotti degli schemi di copertura ottimali per griglie di qualsiasi dimensione e inoltre vengono migliorati i limiti superiori e inferiori noti del numero di Dominazione Romana. Per quanto riguarda i grafi bipartiti viene proposto un approccio che partendo da un insieme di vertex cover del grafo produce una funzione di Dominazione Romana in tempo polinomiale. Nel prosieguo della dissertazione vengono mostrati vari approcci euristici per qualsiasi classe di grafo. In particolare viene prodotto un algoritmo euristico che in tempo polinomiale calcola una copertura e un numero di Dominazione Romana che rientra nei limiti teorici noti introducendo un nuovo parametro associato ai vertici del grafo. Infine una delle varianti della stessa euristica è stata implementata su architettura CUDA permettendo la parallelizzazione del calcolo su GPU e saranno mostrate le strutture dati utilizzate e le problematiche riscontrate.

Nous cherchons à prouver de nouveaux résultats en théorie des graphes et combinatoire grâce à la vitesse de calcul des ordinateurs, couplée à des algorithmes astucieux. Nous traitons quatre problèmes. Le théorème des quatre couleurs affirme que toute carte d’un monde où les pays sont connexes peut être coloriée avec 4 couleurs sans que deux pays voisins aient la même couleur. Il a été le premier résultat prouvé en utilisant l'ordinateur, en 1989. Nous souhaitions automatiser encore plus cette preuve. Nous expliquons la preuve et fournissons un programme qui permet de la réétablir, ainsi que d'établir d'autres résultats avec la même méthode. Nous donnons des pistes potentielles pour automatiser la recherche de règles de déchargement.Nous étudions également les problèmes de domination dans les grilles. Le plus simple est celui de la domination. Il s'agit de mettre des pierres sur certaines cases d'une grille pour que chaque case ait une pierre, ou ait une voisine qui contienne une pierre. Ce problème a été résolu en 2011 en utilisant l’ordinateur pour prouver une formule donnant le nombre minimum de pierres selon la taille de la grille. Nous adaptons avec succès cette méthode pour la première fois pour des variantes de la domination. Nous résolvons partiellement deux autres problèmes et fournissons des bornes inférieures pour ces problèmes pour les grilles de taille arbitraire.Nous nous sommes aussi penchés sur le dénombrement d’ensembles dominants. Combien y a-t-il d’ensembles dominant une grille donnée ? Nous étudions ce problème de dénombrement pour la domination et trois variantes. Nous prouvons l'existence de taux de croissance asymptotiques pour chacun de ces problèmes. Pour chaque, nous donnons en plus un encadrement de son taux de croissance asymptotique.Nous étudions enfin les polyominos, et leurs façons de paver des rectangles. Il s'agit d'objets généralisant les formes de Tetris : un ensemble de carrés connexe (« en un seul morceau »). Nous avons attaqué un problème posé en 1989 : existe-t-il un polyomino d'ordre impair ? Il s'agit de trouver un polyomino qui peut paver un rectangle avec un nombre impair de copies, mais ne peut paver de rectangle plus petit. Nous n'avons pas résolu ce problème, mais avons créé un programme pour énumérer les polyominos et essayer de trouver leur ordre, en éliminant ceux ne pouvant pas paver de rectangle. Nous établissons aussi une classification, selon leur ordre, des polyominos de taille au plus 18
Our goal is to prove new results in graph theory and combinatorics thanks to the speed of computers, used with smart algorithms. We tackle four problems.The four-colour theorem states that any map of a world where all countries are made of one part can be coloured with 4 colours such that no two neighbouring countries have the same colour. It was the first result proved using computers, in 1989. We wished to automatise further this proof. We explain the proof and provide a program which proves it again. It also makes it possible to obtain other results with the same method. We give potential leads to automatise the search for discharging rules.We also study the problems of domination in grids. The simplest one is the one of domination. It consists in putting a stone on some cells of a grid such that every cell has a stone, or has a neighbour which contains a stone. This problem was solved in 2011 using computers, to prove a formula giving the minimum number of stones needed depending on the dimensions of the grid. We successfully adapt this method for the first time for variants of the domination problem. We solve partially two other problems and give for them lower bounds for grids of arbitrary size.We also tackled the counting problem for dominating sets. How many dominating sets are there for a given grid? We study this counting problem for the domination and three variants. We prove the existence of asymptotic growths rates for each of these problems. We also give bounds for each of these growth rates.Finally, we study polyominoes, and the way they can tile rectangles. They are objects which generalise the shapes from Tetris: a connected (of only one part) set of squares. We tried to solve a problem which was set in 1989: is there a polyomino of odd order? It consists in finding a polyomino which can tile a rectangle with an odd number of copies, but cannot tile any smaller rectangle. We did not manage to solve this problem, but we made a program to enumerate polyominoes and try to find their orders, discarding those which cannot tile rectangles. We also give statistics on the orders of polyominoes of size up to 18

De nombreux problèmes algorithmiques sont « difficiles », dans le sens où on ne sait pas les résoudre en temps polynomial par rapport à la taille de l’entrée, soit parce qu’ils sont NP-difficiles, soit, pour certains problèmes d’énumération, à cause du nombre exponentiel d'objets à énumérer. Depuis une quinzaine d’années on trouve un intérêt grandissant dans la littérature pour la conception d'algorithmes exacts sophistiqués afin de les résoudre le plus efficacement possible. Dans le cadre de cette thèse, nous nous intéressons à la conception d'algorithmes exacts exponentiels autour de trois problèmes difficiles. Nous étudions tout d'abord le problème d'optimisation Ensemble Connexe Tropical pour lequel nous décrivons un algorithme afin de le résoudre en général, puis un algorithme de branchement plus rapide pour le résoudre sur les arbres, ce problème restant difficile même dans ce cas. Nous nous intéressons ensuite au problème d'énumération Ensembles Dominants Minimaux, pour lequel nous donnons des algorithmes résolvant ce problème dans les graphes splits, cobipartis, ainsi que dans les graphes d'intervalles. Nous déduisons des bornes supérieures sur le nombre d'ensembles dominants minimaux admis par de tels graphes. La dernière étude de cette thèse concerne le problème d'optimisation Domination Romaine Faible dans lequel, étant donné un graphe nous cherchons à construire une fonction de pondération selon certaines propriétés. Le problème est NP-difficile en général, mais nous donnons un algorithme glouton linéaire calculant une telle fonction pour les graphes d'intervalles
Many algorithmic problems are « hard », in the sense of we do not know how to solve them in polynomialtime, either because they are NP-hard, or, for some enumeration problems, because the number of objectsto be produced is exponential. During the last fifteen years there was a growing interest in the design of exact algorithms to solve such problems as efficiently as possible. In the context of this thesis, we focus on the design of exponential exact algorithms for three hard problems. First, we study the optimisation problem Tropical Connected Set for which we describe an algorithm to solve it in the general case, then a faster branch-and-reduce algorithm to solve it on trees; the problem remains difficult even in this case. Secondly we focus on the Minimal Dominating Sets enumeration problem, for which we give algorithms to solve it on split, cobipartite and intervals graphs. As a byproduct, we establish upper bounds on the number of minimal dominating sets in such graphs. The last focus of this thesis concerns the Weak Roman Domination optimisation problem for which, given a graph, the goal is to build a weight function under some properties. The problem is NP-hard in general, but we give a linear greedy algorithm which computes such a function on interval graphs

L’œuvre de la romancière libanaise ‘Alawiyya Ṣubḥ (née à Beyrouth en 1955) est traversée par un rapport intrinsèque entre le corps épanoui et son exercice de la parole, de même qu’entre le corps réprimé et son embrigadement dans le silence, le tout lié à une peur du féminin dans ses manifestations aussi bien corporelles que langagières. Face à la norme répressive, le langage des personnages, lieu de l’articulation du savoir et du pouvoir, comme leur corps, lieu de l’exercice de la domination masculine, deviennent des lieux de contre-pouvoirs, des « subjectivités » en devenir comme dirait Michel Foucault. Ainsi se pose dans les trois romans de Ṣubḥ : Maryam al-ḥakāyā (2002), Dunyā (2006) et Ismuhu l-ġarām (2009) la question de la représentation des femmes et la possibilité qu’elles ont de prendre ou non la parole et de se faire entendre. Dans le système patriarcal mis en scène dans ces romans, le silence est la norme contre laquelle s’élève la voix de certains personnages, femmes et hommes. Par conséquent, quand elle intervient, leur parole, qui se situe aux confins de l’admissible, du convenable et du soutenable, a tout de suite valeur de transgression. Une fois cette parole advenue, la femme, parce que c’est surtout d’elle qu’il s’agit, récupère sa voix et l’image de son corps, ce dernier étant, en quelque sorte, le premier lieu où se manifeste l’appropriation patriarcale du discours féminin, et sa réappropriation par la femme, le premier et principal signe d’une possible émancipation. Un parler « féminin » est alors célébré, un parler qui n’est pas exclusivement de femmes, mais un parler qui ne prétend pas à l’universel, et qui permet l’émergence d’un discours minoritaire échappant à la vision logocentrique et théocentrique du monde
The work of the Lebanese novelist 'Alawiyya Ṣubḥ (Beirut, 1955) is traversed by an intrinsic relationship between the unimpeded body and its exercise of speech, likewise between the repressed body and its enslavement in silence, all being linked to a fear of what feminine would be in its corporal and linguistic manifestations. Faced with the repressive norms, the language of the characters being a place where power and knowledge articulate on the one hand and their body, as the place of the exercise of male domination on the other hand, become places of counter power. In other hands, they become places of upcoming "subjectivities", as Michel Foucault would say. In the three novels of Ṣubḥ: Maryam al-ḥakāyā (2002), Dunyā (2006) and Ismuhu l-ġarām (2009), arises the question of the representation of women and the possibility for them to be voiced and heard. In the patriarchal system depicted in these novels, silence is the norm against which the voice of certain women and men rises. Therefore, when their word intervene, lying at the confines of the admissible, the suitable and the sustainable, it has immediately the value of transgression. Once this word has come, the woman, main subject of this word, recovers her voice and the image of her body. The body is the first place where the patriarchal appropriation of feminine discourse manifests itself, and the reappropriation of this discourse by woman becomes the first and principal sign of a possible emancipation. A « feminin » speech is then celebrated, a speech that is not exclusively that of women, yet a speech that does not pretend to the universal, and which allows the emergence of a minority discourse that escapes the logocentric and theocentric visions of the world

碩士
國立臺灣大學
數學研究所
97
A Roman dominating function of a graph G is a function f : V (G) → {0, 1, 2} such that whenever f(v) = 0 there xists a vertex u adjacent to v such that f(u) = 2. The weight of f is w(f) = Pv∈V (G) f(v). The Roman domination number γR(G) of G is the minimum weight of a Roman dominating function of G. In this thesis, we give linear time algorithms for finding Roman domination numbers of interval graphs and strongly chordal graphs. We also give sharp upper bounds of Roman domination numbers for some classes of graphs.

碩士
淡江大學
數學學系碩士班
102
Given a graph G = (V, E). We define a function f from V to {0, 1, 2}. The function f is called a Roman dominating function on G when satisfying the condition that every vertex v_i with f(v_i)=0 must be adjacent to at least one vertex v_j with f(v_j)=2. The weight of Roman dominating function f is the sum of the weight of each vertex of G. The minimum weight of all possible Roman dominating functions on G is the Roman domination number of G, denoted by γ_R (G). A spider graph G(k_1,k_2,k_3,…,k_t ) is the union of t paths〖 P〗_(k_1 ), 〖 P〗_(k_2 ), …, 〖 P〗_(k_t )with one common end vertex. A generalized spider graph〖 C〗_t (k_1,k_2,k_3,…,k_t ) is the union of a t-cycle〖 C〗_t=(1,2,3,…,t) and t paths〖 P〗_(k_1 ), 〖 P〗_(k_2 ), …, 〖 P〗_(k_t ) where each path intersect Ct with exact one vertex and〖 P〗_(k_i ) intersect Ct at the vertex i. In this thesis, we obtain the formula to calculate the minimum domination number and Roman domination number of each spider graph. For the Roman domination number of a generalized spider graph, we obtain the formula of γ_R (C_3 (k_(1 ), k_2, k_3 )) and γ_R (C_4 (k_1,k_2,k_3,k_4 )) related to the Roman domination number of a spider graph. After that we give two conjectures about calculating γ_R (C_5 (n_1,n_2,n_3,n_4,n_5 )) and γ_R (C_6 (n_1,n_2,n_3,n_4,n_5,n_6 )).

碩士
國立清華大學
資訊工程學系
95
A roman domination problem is quite a hot variant domination problem in recent years. In one graph G = (V, E), a roman domination function is a function f : V �� {0, 1, 2}, that each one vertex u with f(u) = 0 is adjacent to at least one vertex v with f(v) = 2, among them u and v belongs to V. The weight of a roman domination function f is the sum of the weight of V. A roman domination number of a graphs G is the smallest weight of the possible roman domination function f. When give one permutation graph, we can provide a polynomial algorithm (O(n5))to find out the roman domination number by using the method of dynamic programming. It checks all the possible order cross pairs. With regard to each order cross pair, we find out the best solution for it at that time. Finally we combine the solution to solve roman dominating function.

碩士
國立東華大學
資訊工程學系
95
A Roman dominating function on a graph G = (V, E) is a function f : V → f(0, 1, 2) satisfying that every vertex u with f(u) = 0 has a neighbor v with f(v) = 2. The weight of the Roman dominating function f is the sum of f(v) for the vertices belonging to V. The Roman domination number of a graph G is the minimum weight of all possible Roman dominating functions on G. The motivation of Roman domination is in assigning the minimum armies to protect all castles and villages at the age of Roman Empire. If two armies locate in an area, they can protect the area that they located and those areas that are their neighborhood. If an area is assigned an army, the army can protect only the place that they located. In this thesis, we consider the Roman domination problem on graphs of bounded treewidth. By using a nice tree decomposition T of the input graph G, our algorithm works from leaves to the root of T. Since the treewidth of G is bounded, the time for computing the information of each node of T is constant. Thus, we obtain a linear-time algorithm for the Roman domination problem on bounded treewidth graphs.

This master thesis deals with feminist literary analysis of the works of writer Michal Viewegh, specifically his two prose novels Román pro ženy and Román pro muže using a method called resistant reading with a critical gender analysis and subsequent final comparison. This thesis consists of two parts, from the theoretical - methodological, which outlines the theoretical basis for the next analytical part. The key concepts are in the first part the researches of literary critics on Michal Viewegh, theories of Judith Fetterley, Elaine Showalter and Janice A. Radway. Furthermore, there are the theoretical basis of gender, and how gender stereotypes are constructed. This section is mainly based on the theorists Blanka Knotková - Čapková, Annis Pratt, Claire M. Renzetti and Daniel J. Curran and founder of analytical psychology Carl Gustav Jung. In describing femininity and masculinity are central lines theories of Naomi Wolf, Simone de Beauvoir and Pierre Bourdieu, Michael Kimmel and Robert Bly. The analytical part is the critical uncovering of gender stereotypes and power discourse. The conclusion is made by the final critical comparison of both novels. Key words: resistant reading, literary canon, gender stereotypes, masculinity, femininity, beauty myth, male domination, power