Let G=(V,E) be a graph with vertex set V and edge set E. A vertex v∈V ve-dominates every edge incident to it as well as every edge adjacent to these incident edges. The vertex–edge degree of a vertex v is the number of edges ve-dominated by v. Similarly, an edge e=uv ev-dominates the two vertices u and v incident to it, as well as every vertex adjacent to u or v. The edge–vertex degree of an edge e is the number of vertices ev-dominated by edge e. In this paper we introduce these types of degrees and study their properties.

Thesis (PhD)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: The domination number of a graph is the cardinality of a smallest subset of its vertex set with the property that each vertex of the graph is in the subset or adjacent to a vertex in the subset. This graph parameter has been studied extensively since its introduction during the early 1960s and finds application in the generic setting where the vertices of the graph denote physical entities that are typically geographically dispersed and have to be monitored efficiently, while the graph edges model links between these entities which enable guards, stationed at the vertices, to monitor adjacent entities. In the above application, the guards remain stationary at the entities. In 2005, this constraint was, however, relaxed by the introduction of a new domination-related parameter, called the secure domination number. In this relaxed, dynamic setting, each unoccupied entity is defended by a guard stationed at an adjacent entity who can travel along an edge to the unoccupied entity in order to resolve a security threat that may occur there, after which the resulting configuration of guards at the entities is again required to be a dominating set of the graph. The secure domination number of a graph is the smallest number of guards that can be placed on its vertices so as to satisfy these requirements. In this generalised setting, the notion of edge removal is important, because one might seek the cost, in terms of the additional number of guards required, of protecting the complex of entities modelled by the graph if a number of edges in the graph were to fail (i.e. a number of links were to be eliminated form the complex, thereby disqualifying guards from moving along such disabled links). A comprehensive survey of the literature on secure graph domination is conducted in this dissertation. Descriptions of related, generalised graph protection parameters are also given. The classes of graphs with secure domination number 1, 2 or 3 are characterised and a result on the number of defenders in any minimum secure dominating set of a graph without end-vertices is presented, after which it is shown that the decision problem associated with computing the secure domination number of an arbitrary graph is NP-complete. Two exponential-time algorithms and a binary programming problem formulation are presented for computing the secure domination number of an arbitrary graph, while a linear algorithm is put forward for computing the secure domination number of an arbitrary tree. The practical efficiencies of these algorithms are compared in the context of small graphs. The smallest and largest increase in the secure domination number of a graph are also considered when a fixed number of edges are removed from the graph. Two novel cost functions are introduced for this purpose. General bounds on these two cost functions are established, and exact values of or tighter bounds on the cost functions are determined for various infinite classes of special graphs. Threshold information is finally established in respect of the number of possible edge removals from a graph before increasing its secure domination number. The notions of criticality and stability are introduced and studied in this respect, focussing on the smallest number of arbitrary edges whose deletion necessarily increases the secure domination number of the resulting graph, and the largest number of arbitrary edges whose deletion necessarily does not increase the secure domination number of the resulting graph. / AFRIKAANSE OPSOMMING: Die dominasiegetal van ’n grafiek is die kardinaalgetal van ’n kleinste deelversameling van die grafiek se puntversameling met die eienskap dat elke punt van die grafiek in die deelversameling is of naasliggend is aan ’n punt in die deelversameling. Hierdie grafiekparameter is sedert die vroeë 1960s uitvoerig bestudeer en vind toepassing in die generiese situasie waar die punte van die grafiek fisiese entiteite voorstel wat tipies geografies verspreid is en doeltreffend gemonitor moet word, terwyl die lyne van die grafiek skakels tussen hierdie entiteite voorstel waarlangs wagte, wat by die entiteite gebaseer is, naasliggende entiteite kan monitor. In die bogenoemde toepassing, bly die wagte bewegingloos by die fisiese entiteite waar hulle geplaas word. In 2005 is hierdie beperking egter verslap met die daarstelling van ’n nuwe dominasie-verwante grafiekparameter, bekend as die sekure dominasiegetal. In hierdie verslapte, dinamiese situasie word elke punt sonder ’n wag deur ’n wag verdedig wat by ’n naasliggende punt geplaas is en wat langs die verbindingslyn na die leë punt kan beweeg om daar ’n bedreiging te neutraliseer, waarna die gevolglike plasing van wagte weer ’n dominasieversameling van die grafiek moet vorm. Die sekure dominasiegetal van ’n grafiek is die kleinste getal wagte wat op die punte van die grafiek geplaas kan word om aan hierdie vereistes te voldoen. Die beginsel van lynverwydering speel ’n belangrike rol in hierdie veralgemeende situasie, omdat daar gevra mag word na die koste, in terme van die addisionele getal wagte wat vereis word, om die kompleks van entiteite wat deur die grafiek gemodelleer word, te beveilig indien ’n aantal lynfalings in die grafiek plaasvind (m.a.w. indien ’n aantal skakels uit die kompleks van entiteite verwyder word, en wagte dus nie meer langs sulke skakels mag beweeg nie). ’n Omvattende literatuurstudie oor sekure dominasie van grafieke word in hierdie verhandeling gedoen. Beskrywings van verwante, veralgemeende verdedigingsparameters in grafiekteorie word ook gegee. Die klasse van grafieke met sekure dominasiegetal 1, 2 of 3 word gekarakteriseer en ’n resultaat oor die getal verdedigers in enige kleinste sekure dominasieversameling van ’n grafiek sonder endpunte word daargestel, waarna daar getoon word dat die beslissingsprobleem onderliggend aan die berekening van die sekure dominasiegetal van ’n arbitrêre grafiek NP- volledig is. Twee eksponensiële-tyd algoritmes en ’n binêre programmeringsformulering word vir die bepaling van die sekure dominasiegetal van ’n arbitrêre grafiek daargestel, terwyl ’n lineêre algoritme vir die berekening van die sekure dominasiegetal van ’n arbitrêre boom ontwerp word. Die praktiese doeltreffendhede van hierdie algoritmes word vir klein grafieke met mekaar vergelyk. Die kleinste en groostste toename in die sekure dominasiegetal van ’n grafiek word ook oorweeg wanneer ’n vaste getal lyne uit die grafiek verwyder word. Twee nuwe kostefunksies word vir hierdie doel daargestel en algemene grense word op hierdie kostefunksies vir arbitrêre grafieke bepaal, terwyl eksakte waardes van of verbeterde grense op hierdie kostefunksies vir verskeie oneindige klasse van spesiale grafieke bereken word. Drempelinligting word uiteindelik bepaal in terme van die moontlike getal lynverwyderings uit ’n grafiek voordat die sekure dominasiegetal daarvan toeneem. Die konsepte van kritiekheid en stabiliteit word in hierdie konteks bestudeer, met ’n fokus op die kleinste getal arbitrêre lynfalings wat noodwendig die sekure dominasiegetal van die gevolglike grafiek laat toeneem, of die grootste getal arbitrêre lynfalings wat noodwendig die sekure dominasiegetal van die gevolglike grafiek onveranderd laat.

La coédition de traductions faites au Québec, puis diffusées sous la marque d’un éditeur français, est une pratique à laquelle ont recours les éditeurs pour accroître le rayonnement de leurs titres. Ces coéditions s’effectuent selon des modalités variées dont l’évolution est parfois imprévisible. Dans le processus, les éditeurs et les traducteurs sont amenés à faire des compromis sur la langue d’arrivée afin de rejoindre les publics cibles outre-Atlantique. En quoi consistent ces compromis? Sont-ils terminologiques, lexicaux, culturels ou purement subjectifs? Comment sont-ils perçus par les traducteurs et les éditeurs? Ce mémoire explore ces questions par le biais de quatre études de cas de coéditions de traductions par des éditeurs et des traducteurs littéraires du Québec. L’analyse montre que ces compromis, qu’ils soient ou non culturels, affectent peu la qualité du français mais qu’ils créent parfois chez les éditeurs et les traducteurs un sentiment de domination culturelle de la part de la France. Ce discours est cependant nuancé par les types de pratiques de coédition et par la position des traducteurs dans la structure de l’édition. Un meilleur encadrement des pratiques de coédition et une valorisation du statut du traducteur dans le champ littéraire pourraient contribuer à atténuer certaines tensions liées à la coédition. / The copublishing of the translated version of literary books in Quebec and then distributed under a French publishing brand, is a practice used by editors to broaden the outreach of their books. The process of copublishing is carried out through various methods which tend to evolve in an unpredictable way : editors and translators make compromises about the target language in order to reach their cross-Atlantic markets. What is the nature of these compromises? Are they terminological, lexicographical, cultural or merely subjective? How are they perceived by translators and publishers? This essay explores these questions through the study of four cases of literary works copublished by publishers and literary translators from Quebec. The analysis demonstrates that these compromises, be they cultural or not, have little impact on the quality of French in the copublishing market, which is often in France. But they sometimes create a feeling of cultural dominance on the part of France. This discourse is however nuanced by the type of copublishing practice and the position occupied by translators within the publishing structure. A clearer framework for copublishing practices and a better status for the translator of literary works would contribute to mitigate some of the tensions related to copublishing.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

L'objectif poursuivi dans ce mémoire est de montrer que le néo-républicanisme possède les outils les plus efficaces pour penser la réconciliation des droits individuels, fondement des États de droits occidentaux contemporains, et des droits collectifs que peuvent légitimement réclamer les collectivités nationales. Dans cette visée, et comme de nombreux auteurs libéraux se sont attaqués à cette question dans les dernières décennies, j'expose d'abord trois stratégies libérales pour traiter cette possible réconciliation tout en faisant ressortir leurs faiblesses respectives. J'avance qu'aucune de ces stratégies ne permet vraiment de comprendre comment un régime de droits collectifs et un régime de droits individuels peuvent être articulés de façon cohérente. J'argue ensuite que le néo-républicanisme, parce qu'il comprend la liberté non pas comme l'absence d'interférence, mais comme un statut de non-domination, permet de voir que les droits collectifs des groupes nationaux et les droits individuels sont nécessairement compatibles, parce qu'ils s'organisent en fonction du même idéal. Les droits d'un individu et ceux de sa collectivité nationale sont, d'une certaine manière, les deux faces d'une même médaille, la non-domination individuelle dépendant de la non-domination du groupe national auquel l'individu appartient. En dernier lieu, je soutiens que cette compréhension du rapport entre les deux régimes de droits devrait se traduire par un ensemble de mesures institutionnelles concrètes dont la plus importante est la reconnaissance d'un droit, pour les collectivités nationales, à l'autodétermination. / The purpose of this M.A. research is to show that neo-republicanism provides the most efficient tools to think the reconciliation of a system of individual rights, upon which western contemporary states and their rule of law are based, and of a system of collective rights that can legitimately be claimed by national collectivities. Since the issue of the compatibility of individual and collective rights has mainly been tackled by liberals, I begin by presenting three liberal strategies to deal with this possible reconciliation and I try to highlight their insufficiencies. I claim that none of those strategies actually provide a consistent way to understand how a system of individual rights and a system of collective rights can coherently be articulated. I then argue that neo-republicanism, for it conceptualizes liberty not as the absence of interference, but as the absence of domination, makes apparent that national collectivities’ rights and individual rights are necessarily compatible since they spring from the same ideal. The rights of an individual and the rights of its national collectivity are, in a way, the two sides of the same coin, for individual non-domination depends upon the non- domination of the national group to which the individual belongs. Lastly, I claim that grasping the relationship between the two systems of rights in this manner should be reflected by a set of concrete institutional measures, the most important being the recognition of a right, for national collectivities, to self-determination.

Ce mémoire est l'occasion d'établir une courte généalogie des femmes vampires au cinéma, en mettant en avant la manière dont la figure de la femme vampire résonne avec celle de la femme fatale, dans la mesure où elle constitue à la fois une vision négative de la femme émancipée, tout en offrant une manière d’échapper au modèle féminin traditionnel. En me demandant si le vampirisme peut être une source de pouvoir émancipatoire pour les femmes, j’analyse attentivement Byzantium (2012) de Neil Jordan. À travers l’étude successive des deux personnages principaux, Clara et Eleanor, je montre comment le film résonne avec la généalogie des femmes vampires établie préalablement, ainsi qu’avec certains enjeux féministes. Surtout, l’accent est mis sur la manière dont les personnages féminins contestent le pouvoir masculin, à travers la performance des stéréotypes, pour Clara, et la prise de contrôle du récit, pour Eleanor. Enfin, je me concentre sur la manière dont, à travers des mouvements de devenirs, ces personnages sortent du cycle fatal de l’oppression masculiniste, qui mène habituellement à l’extinction de la femme vampire en fin de récit, mais qui ici aboutit à une tentative de réconciliation entre les sexes. Mon travail s’appuie sur de larges recherches concernant la figure du vampire, ainsi que sur les études féministes et gender studies relatives aux textes vampiriques. Je m’appuie également sur les réflexions de Judith Butler, les travaux deleuziens sur la notion de « devenir », et les considérations de Derrida sur le don. / This master thesis is the opportunity to establish a short genealogy of vampire women on screen, highlighting how the figure of the vampire resonates with that of the femme fatale, since it is both a negative vision of the emancipated woman, while also providing a way to escape the traditional female model. Wondering if vampirism can be a source of emancipatory power for women, I analyze carefully Byzantium (2012, Neil Jordan). Through successive study of the two main characters, Clara and Eleanor, I show how the film resonates with the genealogy of vampire women established previously, as well as some feminist issues. Above all, the emphasis is on how the female characters are challenging male power, through the performance of stereotypes, for Clara, and through the takeover of the narrative, for Eleanor. Finally, I focus on how, through movements of becomings, these characters come out of the fatal cycle of masculinist oppression, which usually leads to the extinction of the female vampire at the end of the story, but here leads to an attempt at reconciliation between the sexes. My work is based on extensive research on the figure of the vampire, and women and gender studies relating to vampiric texts. I also rely on Judith Butler’s work, the deleuzian concept of “becoming”, and considerations on the gift by Derrida.

Ce travail a pour but d'identifier et d'expliquer l'expression de croyances, notamment religieuses, dans l'enseignement public français et polonais. D'après le dictionnaire Littré, l'« enseignement public » est l'« enseignement que donne l'État ». Si l'on suit cette définition, alors les croyances dont il est question sont celles qui sont exprimées par les personnes chargées de concevoir les programmes scolaires, par les auteurs de manuels scolaires, par les professeurs, etc. La focale sera mise sur l'enseignement (historique, littéraire…) relatif aux religions, parce que c'est là que des croyances religieuses sont a priori le plus susceptibles d'être exprimées. Une distinction majeure proposée est celle entre croyances collectives et croyances personnelles. La France et la Pologne sont des pays très différents, mais des points communs sont repérables. En particulier, dans les deux pays en question, il arrive que des croyances exprimées dans l'enseignement public interfèrent arbitrairement avec certaines croyances que peuvent avoir les élèves – même si cette interférence arbitraire semble moindre en France qu'en Pologne. Finalement, notre étude voudrait établir que l'expression de croyances personnelles ou collectives dans l'enseignement public engendre parfois de la domination. L'originalité la plus nette de cette thèse est probablement de chercher à mettre en évidence la pertinence empirique d'analyses conceptuelles proposées par des philosophes sociaux que l'on pourrait qualifier de « néo-holistes » (Margaret Gilbert, Raimo Tuomela, Philip Pettit) et dont le souci commun est de reformuler avec davantage de rigueur analytique certaines intuitions de Durkheim. / This work aims to identify and to explain the expression of beliefs, especially religious ones, in public teaching. According to the Littré dictionary, public teaching (enseignement public) is the teaching given by the state. If we follow this definition, then the beliefs in question are those which are expressed by people in charge of conceiving school programs, by textbook authors, by teachers, etc. Focus will be placed on the (historical, literary…) teaching about religions, because religious beliefs are a priori the most likely to be expressed there. A key distinction will be drawn between collective beliefs and personal beliefs. France and Poland are two very different countries, but commonalities can be identified. Specifically, in both countries, it happens that beliefs expressed in public teaching arbitrarily interfere with beliefs which pupils could hold – although this arbitrary interference seems lesser in France than in Poland. Finally, our study seeks to show that the expression of personal or collective beliefs in public teaching sometimes engender domination. One original contribution of this work lies in trying to display the empirical relevance of conceptual analyses which could be qualified as “neo-holists” (Margaret Gilbert, Raimo Tuomela, Philip Pettit) and for which a common concern is to reformulate with more analytical rigor some of Durkheim's intuitions.

Dans cette thèse, nous étudions les jeux combinatoires sousdifférentes contraintes. Un jeu combinatoire est un jeu à deux joueurs, sanshasard, avec information complète et fini acyclique. D’abord, nous regardonsles jeux impartiaux en version normale, en particulier les jeux VertexNimet Timber. Puis nous considérons les jeux partisans en version normale, oùnous prouvons des résultats sur les jeux Timbush, Toppling Dominoeset Col. Ensuite, nous examinons ces jeux en version misère, et étudionsles jeux misères modulo l’univers des jeux dicots et modulo l’univers desjeux dead-endings. Enfin, nous parlons du jeu de domination qui, s’il n’estpas combinatoire, peut être étudié en utilisant des outils de théorie des jeuxcombinatoires. / In this thesis, we study combinatorial games under differentconventions. A combinatorial game is a finite acyclic two-player game withcomplete information and no chance. First, we look at impartial gamesin normal play and in particular at the games VertexNim and Timber.Then, we consider partizan games in normal play, with results on the gamesTimbush, Toppling Dominoes and Col. Next, we look at all these gamesin misère play, and study misère games modulo the dicot universe and modulothe dead-ending universe. Finally, we talk about the domination game which,despite not being a combinatorial game, may be studied with combinatorialgames theory tools.

La reconnaissance est généralement présentée soit comme une réussite soit comme un échec. Pourtant, les nombreux défis qui se présentent actuellement aux sociétés démocratiques occidentales obligent à chercher une porte de sortie à cette alternative tragique. Comment échapper au malheur de la reconnaissance ? La reconnaissance est le concept phare d'un ensemble de théories et de politiques très variées. Elle repose sur des identités et cultures à la base de la diversité. La diversité est la notion derrière laquelle se trouvent des politiques officielles et non-officielles de pluralisme, c'est-à-dire de promotion de la diversité. C'est là le cœur d'un problème majeur, à l'intersection entre politique, sociologie et philosophie. D'un côté la reconnaissance fige les facteurs de diversité ; de l'autre, la diversité, caractérisée par une prolifération d'identités et de cultures potentiellement variables au cours du temps et en partie fluides, bloque le processus de reconnaissance. Comment alors conjuguer diversité et reconnaissance ? En effet, la diversité empêche la reconnaissance et la reconnaissance empêche la diversité. L'une fait obstacle à l'autre. Introduire l'opérateur de l'échec dans le rouage de la diversité et de la reconnaissance permet d'identifier les zones les plus problématiques : les fondements même de la reconnaissance, les modalités de la non-reconnaissance, et la question de la violence, véritable angle-mort des théories et des politiques les plus courantes. Partant de ces difficultés, et après un travail de déconstruction, nous proposons une piste de reconstruction de la reconnaissance ainsi renouvelée, formée de trois pans, sous-tendus par le postulat d'une auto-détermination radicale des individus et des groupes. Le premier pan repose sur la séparation. Elle est résistance à l'uniformisation et à la conversion sous la forme, par exemple, d'une injonction à l'assimilation. Le deuxième pan concerne la diversité comme postulat d'une nouvelle politique de reconnaissance repensée à partir de la diversité. Les conséquences sont plus profondes au niveau individuel que collectif. Le troisième pan a trait au poids du passé dans la reconnaissance : désormais cette reconnaissance-là est sans réconciliation, sans rachat et sans réparation. Elle n'est plus un outil, mais une modalité des relations intersubjectives. Il ne s'agit pas d'ignorer les tragédies passées, bien au contraire ; mais plutôt de les prendre en compte pour élaborer un concept tourné vers l'avenir. / Recognition is typically presented either as a success, or as a failure. However the many challenges presented to Western democratic societies require that we look for a way out of is tragic duality. How can one escape the misfortune of recognition? Recognition is the foundational concept of a diverse array of theories and policies. It is based on the interplay among various identities and cultures which collectively constitute diversity. Diversity is the concept on which official and unofficial policies of pluralism, that is to say policies to promote diversity, are based. This is the heart of a significant problem at the intersection of politics, sociology and philosophy. On the one hand, recognition crystallizes factors of diversity. On the other hand, diversity as characterized by a proliferation of cultures that are fluid and potentially variable over time, blocks the recognition process. How then to combine diversity and recognition? Diversity prevents recognition and recognition prevents diversity. One precludes the other. Introducing the notion of failure in the interplay between diversity and recognition permits one to identify the most problematic areas: the very foundation of recognition, the terms of non-recognition, and the issue of violence which is the real blind-spot of the most common theories and policies. From these difficulties, and after an exercise in deconstruction, we propose a reconstruction of the concept of recognition, a renewed track, consisting of the sections underpinned by the postulate of the radical self-determination of individuals and groups. The first aspect rests on separation. Separation is resistance to conformity and conversion in the form, for example of an obligation to forced assimilation. The second aspect concerns diversity as a premise for a new policy of recognition conceived from the standpoint of diversity. The effects of this new policy are more significant at the individual level than at the collective level. The third aspect relates to the importance of the past assigned to recognition. This redesigned concept of recognition is without reconciliation, without atonement, and without compensation. This is not to ignore past tragedies, quite the contrary; but rather to take them into account in order to look to the future.

Les problèmes de domination (dominant, dominant indépendant, ...) et de couverture (vertex-cover, arbre de Steiner, ...) sont NP-complets. Pour autant, pour la plupart de ces problèmes, il existe toujours une solution constructible en temps polynomial (potentiellement de valeur objective très mauvaise), ou au moins, il est possible de déterminer facilement (en temps polynomial) l'existence ou non d'une solution. Ces problèmes, initialement issus de situations réelles, sont des modélisations simplistes de ces situations. Nous ajoutons donc des contraintes additionnelles modélisant des contraintes pratiques plausibles : les conflits, des paires d'éléments ne pouvant faire simultanément partie d'une solution (modélisant des incompatibilités diverses), la connexité dans un second graphe (les éléments doivent pouvoir communiquer, et le graphe correspondant à ces liens de communication n'est pas forcément le même) et les obligations, des sous-ensembles d'éléments interdépendants devant être ajoutés simultanément à une solution. Notre but ici n'est pas de modéliser un problème réel précis, mais d'étudier la manière dont ces contraintes modifient la complexité des problèmes étudiés. Nous verrons que dans un grand nombre de cas, déterminer l'existence même d'une solution devient difficile, même sans se préoccuper de leur optimisation. Le problème du firefighter modélise des pompiers tentant de contenir un feu se propageant au tour par tour dans un graphe (potentiellement infini). Nous avons étudié ce problème en ajoutant des contraintes sur le déplacement des pompiers (une vitesse de déplacement limitée entre deux tours). Nous verrons que ces contraintes augmentent en général le nombre de pompiers nécessaires mais ne provoquent pas de changements aussi importants que dans les problèmes précédents. / Domination problems (dominating set, independant dominating set, ...) as well as covering problems (vertex-cover, Steiner tree, ...) are NP-complete. However, for most of these problems, it is always possible to construct a (eventually bad) solution in polynomial time, or at least it is possible to determine whether a solution exists. Those problems originally came from industry, but are simplified modelizations of the real life problems. We add additional constraints modeling plausible practical constraints : conflicts which are pairs of elements that cannot apear simultaneously in a solution (to modelize various incompatibilities), connexity in a second graph (elements of the solution must be able to communicate, and the communication links are a second graph), and obligations which are subsets of interdependant vertices which must be added simultaneously in a solution.We don't aim to model a specific real-world problem, but to study how these plausible constraints affect the complexity of the studied problems. We will see that, in many cases, even determining the existence of a solution (regardless of its size) become hard. The firefighter problem models firefighters aiming to contain a fire spreading turn by turn in a (eventually infinite) graph. We studied this problem with the addition of deplacement constraints for the firefighters (a limited moving speed between turns). We will see that, most of the time, this constraint increase the number of firefighters necessary to contain the fire, but does not trigger such major change as constraints studied in the others problems.