To see the other types of publications on this topic, follow the link: Domination (Graph theory).
Dissertations / Theses on the topic 'Domination (Graph theory)'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Domination (Graph theory).'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
De, Villiers Anton Pierre. "Edge criticality in secure graph domination." Thesis, Stellenbosch : Stellenbosch University, 2014. http://hdl.handle.net/10019.1/95841.
Full textAbstract:
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.
2
Benecke, Stephen. "Higher order domination of graphs." Thesis, Stellenbosch : University of Stellenbosch, 2004. http://hdl.handle.net/10019.1/16257.
Full textAbstract:
Thesis (MSc)--University of Stellenbosch, 2004.ENGLISH ABSTRACT: Motivation for the study of protection strategies for graphs is rooted in antiquity and has evolved as a subdiscipline of graph theory since the early 1990s. Using, as a point of departure, the notions of weak Roman domination and secure domination (where protection of a graph is required against a single attack) an initial framework for higher order domination was introduced in 2002 (allowing for the protection of a graph against an arbitrary finite, or even infinite, number of attacks). In this thesis, the theory of higher order domination in graphs is broadened yet further to include the possibility of an arbitrary number of guards being stationed at a vertex. The thesis firstly provides a comprehensive survey of the combinatorial literature on Roman domination, weak Roman domination, secure domination and other higher order domination strategies, with a view to summarise the state of the art in the theory of higher order graph domination as at the start of 2004. Secondly, a generalised framework for higher order domination is introduced in two parts: the first catering for the protection of a graph against a finite number of consecutive attacks, and the second concerning the perpetual security of a graph (protection of the graph against an infinite number of consecutive attacks). Two types of higher order domination are distinguished: smart domination (requiring the existence of a protection strategy for any sequence of consecutive attacks of a pre–specified length, but leaving it up to a strategist to uncover such a guard movement strategy for a particular instance of the attack sequence), and foolproof domination (requiring that any possible guard movement strategy be a successful protection strategy for the graph in question). Properties of these higher order domination parameters are examined—first by investigating the application of known higher order domination results from the literature, and secondly by obtaining new results, thereby hopefully improving current understanding of these domination parameters. Thirdly, the thesis contributes by (i) establishing higher order domination parameter values for some special graph classes not previously considered (such as complete multipartite graphs, wheels, caterpillars and spiders), by (ii) summarising parameter values for special graph classes previously established (such as those for paths, cycles and selected cartesian products), and by (iii) improving higher order domination parameter bounds previously obtained (in the case of the cartesian product of two cycles). Finally, a clear indication of unresolved problems in higher order graph domination is provided in the conclusion to this thesis, together with some suggestions as to possibly desirable future generalisations of the theory.
AFRIKAANSE OPSOMMING: Die motivering vir die studie van verdedigingstrategie¨e vir grafieke het sy ontstaan in die antieke wˆereld en het sedert die vroe¨e 1990s as ’n subdissipline in grafiekteorie begin ontwikkel. Deur gebruik te maak van die idee van swak Romynse dominasie en versterkte dominasie (waar verdediging van ’n grafiek teen ’n enkele aanval vereis word) het ’n aanvangsraamwerk vir ho¨er– orde dominasie (wat ’n grafiek teen ’n veelvuldige, of selfs oneindige aantal, aanvalle verdedig) in 2002 die lig gesien. Die teorie van ho¨er–orde dominasie in grafieke word in hierdie tesis verbreed, deur toe te laat dat ’n arbitrˆere aantal wagte by elke punt van die grafiek gestasioneer mag word. Eerstens voorsien die tesis ’n omvangryke oorsig van die kombinatoriese literatuur oor Romynse dominasie, swak Romynse dominasie, versterkte dominasie en ander ho¨er–orde dominasie strategie ¨e, met die doel om die kundigheid betreffende die teorie van ho¨er–orde dominasie, soos aan die begin van 2004, op te som. Tweedens word ’n veralgemeende raamwerk vir ho¨er–orde dominasie bekendgestel, en wel in twee dele. Die eerste deel maak voorsiening vir die verdediging van ’n grafiek teen ’n eindige aantal opeenvolgende aanvalle, terwyl die tweede deel betrekking het op die oneindige sekuriteit van ’n grafiek (verdediging teen ’n oneindige aantal opeenvolgende aanvalle). Daar word tussen twee tipes h¨oer–orde dominasie onderskei: intelligente dominasie (wat slegs die bestaan van ’n verdedigingstrategie vir enige reeks opeenvolgende aanvalle vereis, maar dit aan ’n strateeg oorlaat om ’n suksesvolle bewegingstrategie vir die verdediging teen ’n spesifieke reeks aanvalle te vind), en onfeilbare dominasie (wat vereis dat enige moontlike bewegingstrategie resulteer in ’n suksesvolle verdedigingstrategie vir die betrokke grafiek). Eienskappe van hierdie ho¨er–orde dominasie parameters word ondersoek, deur eerstens die toepasbaarheid van bekende ho¨er–orde dominasie resultate vanuit die literatuur te assimileer, en tweedens nuwe resultate te bekom, in die hoop om die huidige kundigheid met betrekking tot hierdie dominasie parameters te verbreed. Derdens word ’n bydrae gelewer deur (i) ho¨er–orde dominasie parameterwaardes vas te stel vir sommige spesiale klasse grafieke wat nie voorheen ondersoek is nie (soos volledig veelledige grafieke, wiele, ruspers en spinnekoppe), deur (ii) parameterwaardes wat reeds bepaal is (soos byvoorbeeld di´e vir paaie, siklusse en sommige kartesiese produkte) op te som, en deur (iii) bekende ho¨er–orde dominasie parametergrense te verbeter (in die geval van die kartesiese produk van twee siklusse). Laastens word ’n aanduiding van oop probleme in die teorie van ho¨er–orde dominasie in die slothoofstuk van die tesis voorsien, tesame met voorstelle ten opsigte van moontlik sinvolle veralgemenings van die teorie.
3
Harutyunyan, Ararat. "Probabilistic methods and domination related problems in graphs." Thesis, McGill University, 2008. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=116070.
Full textAbstract:
A dominating set in a graph is a set S of vertices such that every vertex not in S is adjacent to a member S. A global defensive alliance in a graph is a dominating set S with the property that every vertex in S has in its closed neighborhood at least as many vertices in S as in V -- S. A global offensive alliance in a graph is a dominating set S with the property that every vertex in V -- S has in its closed neighborhood at least as many vertices in S as in V -- S.We first study alliances in graphs. There are many results in this area. For example, it is known that every connected n-vertex graph G has a global offensive alliance of size at most 2n/3. Another result is that any global defensive alliance in G has size at least ( 4n+1 - 1)/2. Our study focuses particularly on trees and algorithms for finding alliances in trees. We find the cardinality of a minimum global offensive alliance for complete k-ary trees and the minimum cardinality global defensive alliance for complete binary and ternary trees. Also, we present a linear time algorithm for finding the minimum global offensive alliance in a tree. Additionally, for a general graph, an upper bound is given on the size of a minimum global offensive alliance in terms its degree sequence. The methods that we use in this part of the thesis are mainly algorithmic and deterministic.
Then we study independent dominating sets in graphs. An independent dominating set is a set of mutually nonadjacent vertices which is also a dominating set. This is a well-studied topic (see Haynes, Hedetniemi and Slater [22]). Our main result is to show that every d-regular graph of order n with girth at least 5 and satisfying d = o(1) and d2(log d)3/2 = o(n) contains an independent dominating set of size at most (1 + o(1)) nlogdd . This generalizes the results of Duckworth and Wormald [15] for random regular graphs. We construct the independent dominating set using recent probabilistic methods which resemble Rodl's semi-random method (see for example Alon and Spencer [1]).
4
Tarr, Jennifer M. "Domination in Graphs." Scholar Commons, 2010. https://scholarcommons.usf.edu/etd/1786.
Full textAbstract:
Vizing conjectured in 1963 that the domination number of the Cartesian product of two graphs is at least the product of their domination numbers; this remains one of the biggest open problems in the study of domination in graphs. Several partial results have been proven, but the conjecture has yet to be proven in general. The purpose of this thesis was to study Vizing's conjecture, related results, and open problems related to the conjecture. We give a survey of classes of graphs that are known to satisfy the conjecture, and of Vizing-like inequalities and conjectures for different types of domination and graph products. We also give an improvement of the Clark-Suen inequality. Some partial results about fair domination are presented, and we summarize some open problems related to Vizing's conjecture.
5
Gardner, Bradley. "Italian Domination on Ladders and Related Products." Digital Commons @ East Tennessee State University, 2018. https://dc.etsu.edu/etd/3509.
Full textAbstract:
An Italian dominating function on a graph $G = (V,E)$ is a function such that $f : V \to \{0,1,2\}$, and for each vertex $v \in V$ for which $f(v) = 0$, we have $\sum_{u\in N(v)}f(u) \geq 2$. The weight of an Italian dominating function is $f(V) = \sum_{v\in V(G)}f(v)$. The minimum weight of all such functions on a graph $G$ is called the Italian domination number of $G$. In this thesis, we will consider Italian domination in various types of products of a graph $G$ with the complete graph $K_2$. We will find the value of the Italian domination number for ladders, specific families of prisms, mobius ladders and related products including categorical products $G\times K_2$ and lexicographic products $G\cdot K_2$. Finally, we will conclude with open problems.
6
Rubalcaba, Roberto Ramon Johnson Peter D. "Fractional domination, fractional packings, and fractional isomorphisms of graphs." Auburn, Ala., 2005. http://repo.lib.auburn.edu/EtdRoot/2005/SPRING/Mathematics/Dissertation/RUBALCABA_ROBERT_56.pdf.
Full text
7
Harris, Elizabeth Marie. "Global Domination Stable Graphs." Digital Commons @ East Tennessee State University, 2012. https://dc.etsu.edu/etd/1476.
Full textAbstract:
A set of vertices S in a graph G is a global dominating set (GDS) of G if S is a dominating set for both G and its complement G. The minimum cardinality of a global dominating set of G is the global domination number of G. We explore the effects of graph modifications on the global domination number. In particular, we explore edge removal, edge addition, and vertex removal.
8
Chukwukere, Presley. "The 2-Domination Number of a Caterpillar." Digital Commons @ East Tennessee State University, 2018. https://dc.etsu.edu/etd/3456.
Full textAbstract:
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.
9
Sterling, Christopher Kent. "Liar's Domination in Grid Graphs." Digital Commons @ East Tennessee State University, 2012. https://dc.etsu.edu/etd/1415.
Full textAbstract:
As introduced by Slater in 2008, liar's domination provides a way of modeling protection devices where one may be faulty. Assume each vertex of a graph G is the possible location for an intruder such as a thief. A protection device at a vertex v is assumed to be able to detect the intruder at any vertex in its closed neighborhood N[v] and identify at which vertex in N[v] the intruder is located. A dominating set is required to identify any intruder's location in the graph G, and if any one device can fail to detect the intruder, then a double-dominating set is necessary. Stronger still, a liar's dominating set can identify an intruder's location even when any one device in the neighborhood of the intruder vertex can lie, that is, any one device in the neighborhood of the intruder vertex can misidentify any vertex in its closed neighborhood as the intruder location or fail to report an intruder in its closed neighborhood. In this thesis, we present the liar's domination number for the finite ladders, infinite ladder, and infinite P_3 x P_infty. We also give bounds for other grid graphs.
10
Carney, Nicholas. "Roman Domination Cover Rubbling." Digital Commons @ East Tennessee State University, 2019. https://dc.etsu.edu/etd/3617.
Full textAbstract:
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.
11
Coetzer, Audrey. "Criticality of the lower domination parameters of graphs." Thesis, Link to the online version, 2007. http://hdl.handle.net/10019/1051.
Full text
12
Smithers, Dayna Brown. "Graph Theory for the Secondary School Classroom." Digital Commons @ East Tennessee State University, 2005. https://dc.etsu.edu/etd/1015.
Full textAbstract:
After recognizing the beauty and the utility of Graph Theory in solving a variety of problems, the author decided that it would be a good idea to make the subject available for students earlier in their educational experience. In this thesis, the author developed four units in Graph Theory, namely Vertex Coloring, Minimum Spanning Tree, Domination, and Hamiltonian Paths and Cycles, which are appropriate for high school level.
13
Russell, Haley D. "Italian Domination in Complementary Prisms." Digital Commons @ East Tennessee State University, 2018. https://dc.etsu.edu/etd/3429.
Full textAbstract:
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.
14
England, Alyssa. "Trees with Unique Italian Dominating Functions of Minimum Weight." Digital Commons @ East Tennessee State University, 2020. https://dc.etsu.edu/etd/3741.
Full textAbstract:
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.
15
Delgado, Pamela I. "Bipartitions Based on Degree Constraints." Digital Commons @ East Tennessee State University, 2014. https://dc.etsu.edu/etd/2410.
Full textAbstract:
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.
16
Whisenant, Christopher. "Parity Domination in Product Graphs." VCU Scholars Compass, 2011. http://scholarscompass.vcu.edu/etd/2522.
Full textAbstract:
An odd open dominating set of a graph is a subset of the graph’s vertices with the property that the open neighborhood of each vertex in the graph contains an odd number of vertices in the subset. An odd closed r-dominating set is a subset of the graph’s vertices with the property that the closed r-ball centered at each vertex in the graph contains an odd number of vertices in the subset. We first prove that the n-fold direct product of simple graphs has an odd open dominating set if and only if each factor has an odd open dominating set. Secondly, we prove that the n-fold strong product of simple graphs has an odd closed r-dominating set if and only if each factor has an odd closed r-dominating set.
17
Jamieson, William. "General Bounds on the Downhill Domination Number in Graphs." Digital Commons @ East Tennessee State University, 2013. https://dc.etsu.edu/honors/107.
Full textAbstract:
A path π = (v1, v2,...vk+1) in a graph G = (V,E) is a downhill path if for every i, 1 < i < k, deg(vi) > deg(vi+1), where deg(vi) denotes the degree of vertex vi ∊ V. The downhill domination number equals the minimum cardinality of a set S ⊂ V having the property that every vertex v ∊ V lies on a downhill path originating from some vertex in S. We investigate downhill domination numbers of graphs and give upper bounds. In particular, we show that the downhill domination number of a graph is at most half its order, and that the downhill domination number of a tree is at most one third its order. We characterize the graphs obtaining each of these bounds.
18
Cheney, Stephen R. "Domination Numbers of Semi-strong Products of Graphs." VCU Scholars Compass, 2015. http://scholarscompass.vcu.edu/etd/3989.
Full textAbstract:
This thesis examines the domination number of the semi-strong product of two graphs G and H where both G and H are simple and connected graphs. The product has an edge set that is the union of the edge set of the direct product of G and H together with the cardinality of V(H), copies of G. Unlike the other more common products (Cartesian, direct and strong), the semi-strong product is neither commutative nor associative.
The semi-strong product is not supermultiplicative, so it does not satisfy a Vizing like conjecture. It is also not submultiplicative so it shares these two properties with the direct product.
After giving the basic definitions related with graphs, domination in graphs and basic
properties of the semi-strong product, this paper includes a general upper bound for the
domination of the semi-strong product of any two graphs G and H as less than or equal to twice the domination numbers of each graph individually. Similar general results for the semi-strong product perfect-paired domination numbers of any two graphs G and H, as well as semi-strong products of some specific types of cycle graphs are also addressed.
19
Vaughan, Lamont D. "Double Domination of Complementary Prisms." Digital Commons @ East Tennessee State University, 2008. https://dc.etsu.edu/etd/1983.
Full textAbstract:
The complementary prism of a graph G is obtained from a copy of G and its complement G̅ by adding a perfect matching between the corresponding vertices of G and G̅. For any graph G, a set D ⊆ V (G) is a double dominating set (DDS) if that set dominates every vertex of G twice. The double domination number, denoted γ×2(G), is the cardinality of a minimum double dominating set of G. We have proven results on graphs of small order, specific families and lower bounds on γ×2(GG̅).
20
Jackson, Eugenie Marie. "Explorations in the classification of vertices as good or bad." [Johnson City, Tenn. : East Tennessee State University], 2001. http://etd-submit.etsu.edu/etd/theses/available/etd-0310101-153932/unrestricted/jacksone.pdf.
Full text
21
Dautermann, Robert Elmer III. "Vertices in Total Dominating Sets." Digital Commons @ East Tennessee State University, 2000. https://dc.etsu.edu/etd/5.
Full textAbstract:
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.
22
Gründlingh, Werner R. "Two new combinatorial problems involving dominating sets for lottery schemes /." Link to the online version, 2004. http://hdl.handle.net/10019.1/1388.
Full text
23
DesOrmeaux, Wyatt Jules. "Restrained and Other Domination Parameters in Complementary Prisms." Digital Commons @ East Tennessee State University, 2008. https://dc.etsu.edu/etd/1998.
Full textAbstract:
In this thesis, we will study several domination parameters of a family of graphs known as complementary prisms. We will first present the basic terminology and definitions necessary to understand the topic. Then, we will examine the known results addressing the domination number and the total domination number of complementary prisms. After this, we will present our main results, namely, results on the restrained domination number of complementary prisms. Subsequently results on the distance - k domination number, 2-step domination number and stratification of complementary prisms will be presented. Then, we will characterize when a complementary prism is Eulerian or bipartite, and we will obtain bounds on the chromatic number of a complementary prism. We will finish the thesis with a section on possible future problems.
24
Mc, Inerney Fionn. "Jeux de domination et d’identification dans les graphes." Thesis, Université Côte d'Azur (ComUE), 2019. http://www.theses.fr/2019AZUR4049.
Full textAbstract:
Dans cette thèse, les jeux à 2 joueurs dans les graphes et leurs aspects algorithmiques et structurels sont étudiés. Nous explorons tout d'abord le jeu de domination éternelle ainsi que sa généralisation, le jeu de l'espion, deux jeux qui reposent sur les ensembles dominants dynamiques. Dans ces deux jeux, une équipe de gardes poursuit un attaquant ou espion rapide dans un graphe, avec l'objectif de rester près de lui éternellement. Le but est de calculer le nombre de domination éternelle (nombre de gardes pour le jeu de l'espion) qui est le nombre minimum de gardes nécessaires pour réaliser l'objectif. La dimension métrique des digraphes et une version séquentielle de la dimension métrique des graphes sont aussi étudiées. Ces deux problèmes ont pour objectif de trouver un sous-ensemble de sommets de taille minimum tel que tous les sommets du graphe sont identifiés uniquement par leurs distances aux sommets du sous-ensemble. En particulier, dans ce dernier problème, on peut "interroger" un certain nombre de sommets par tour. Les sommets interrogés retournent leurs distances à une cible cachée. Le but est de minimiser le nombre de tours nécessaires pour localiser la cible. Ces jeux et problèmes sont étudiés pour des classes de graphe particulières et leurs complexités temporelles sont aussi étudiées. Précisément, dans le Chapitre 3, il est démontré que le jeu de l'espion est NP-difficile et les nombres de gardes des chemins et des cycles sont présentés. Ensuite, des résultats sur le jeu de l'espion dans les arbres et les grilles sont présentés. Notamment, nous démontrons une équivalence entre la variante fractionnaire et la variante "intégrale" du jeu de l'espion dans les arbres qui nous a permis d'utiliser la programmation linéaire pour concevoir ce que nous pensons être le premier algorithme exact qui utilise la variante fractionnaire d'un jeu pour résoudre sa variante "intégrale". Dans le Chapitre 4, des bornes asymptotiques sur le nombre de domination éternelle de la grille du roi sont présentées. Dans le Chapitre 5, des résultats sur la NP-complétude du jeu de Localisation sous différentes conditions (et une variante de ce jeu) sont présentés. Notamment, nous démontrons que le problème est NP-complet dans les arbres. Malgré cela, nous concevons un (+1)-algorithme d'approximation qui résout le problème en temps polynomial. Autant que nous sachions, il n'existe pas d'autres telles approximations pour les jeux dans les graphes. Finalement, dans le Chapitre 6, des résultats sur la dimension métrique des graphes orientés sont présentés. En particulier, les orientations qui maximisent la dimension métrique sont explorées pour les graphes de degré borné, les tores et les grillesIn this thesis, 2-player games on graphs and their algorithmic and structural aspects are studied. First, we investigate two dynamic dominating set games: the eternal domination game and its generalization, the spy game. In these two games, a team of guards pursue a fast attacker or spy in a graph with the objective of staying close to him eternally and one wants to calculate the eternal domination number (guard number in the spy game) which is the minimum number of guards needed to do this. Secondly, the metric dimension of digraphs and a sequential version of the metric dimension of graphs are then studied. These two problems are those of finding a minimum subset of vertices that uniquely identify all the vertices of the graph by their distances from the vertices in the subset. In particular, in the latter, one can probe a certain number of vertices per turn which return their distances to a hidden target and the goal is to minimize the number of turns in order to ensure locating the target. These games and problems are studied in particular graph classes and their computational complexities are also studied. Precisely, in Chapter 3, the NP-hardness of the spy game and the guard numbers of paths and cycles are first presented. Then, results for the spy game on trees and grids are presented. Notably, we show an equivalence between the fractional variant and the "integral" version of the spy game in trees which allowed us to use Linear Programming to come up with what we believe to be the first exact algorithm using the fractional variant of a game to solve the "integral" version. In Chapter 4, asymptotic bounds on the eternal domination number of strong grids are presented. In Chapter 5, results on the NP-completeness of the Localization game under different conditions (and a variant of it) and the game in trees are presented. Notably, we show that the problem is NP-complete in trees, but despite this, we come up with a polynomial-time (+1)-approximation algorithm in trees. We consider such an approximation to be rare as we are not aware of any other such approximation in games on graphs. Lastly, in Chapter 6, results on the metric dimension of oriented graphs are presented. In particular, the orientations which maximize the metric dimension are investigated for graphs of bounded degree, tori, and grids
25
Ho, Yiu Yu. "Global secure sets of trees and grid-like graphs." Doctoral diss., University of Central Florida, 2011. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/4922.
Full textAbstract:
However, as will be demonstrated in Chapter 1, a defensive alliance may not be able to properly defend itself when multiple members are under attack at the same time. The concept of secure sets is introduced in (BDH07) for exactly this purpose. The non-empty set S is a secure set if every subset Xsubset of]S, with the assistance of vertices in S, can successfully defend against simultaneous attacks coming from vertices outside of S. The exact definition of simultaneous attacks and how such attacks may be defended will be provided in Chapter 1. In (BDH07), the authors presented an interesting characterization for secure sets which resembles the definition of defensive alliances. A non-empty set S is a secure set if and only if for all] X subset of] S, vertical line]N (X) intersection] Svertical line] greater than or equal to] vertical line]N(X) - Svertical line] ((BDH07),Theorem 11). The cardinality of a minimum secure set is the security number of G, denoted s(G). A secure set S is a global secure set if it further satisfies N (S)= V. The cardinality of a minimum global secure set of G is the global security number of G, denoted gamma subscript s](G). In this work, we present results on secure sets and global secure sets. In particular, we treat the computational complexity of finding the security number of a graph, present algorithms and bounds for the global security numbers of trees, and present the exact values of the global security numbers of paths, cycles and their Cartesian products.; Let G = (V, E) be a graph and let S subset of] V be a subset of vertices. The set S is a defensive alliance if for all x element of] S, vertical line]N(x)intersection] Svertical line]greater than or equal to] vertical line]N(x) - Svertical line]. The concept of defensive alliances was introduced in (KHH04), primarily for the modeling of nations in times of war, where allied nations are in mutual agreement to join forces if anyone of them is attacked. For a vertex x in a defensive alliance, the number of neighbors of x inside the alliance, plus the vertex x, is at least the number of neighbors of x outside the alliance. In a graph model, the vertices of a graph represent nations and the edges represent country boundaries. Thus, if the nation corresponding to a vertex x is attacked by its neighbors outside the alliance, the attack can be thwarted by x with the assistance of its neighbors in the alliance. In a different subject matter, (FLG00) applies graph theory to model the world wide web, where vertices represent websites and edges represent links between websites. A web community is a subset of vertices of the web graph, such that every vertex in the community has at least as many neighbors in the set as it has outside. So, a web community C satisfies for all] x element of] C, vertical line]N(x) intersection] Cvertical line] greater than] vertical line]N(x) - Cvertical line]. These sets are very similar to defensive alliances. They are known as strong defensive alliances in the literature of alliances in graphs. Other areas of application for alliances and related topics include classification, data clustering, ecology, business and social networks. Consider the application of modeling nations in times of war introduced in the first paragraph. In a defensive alliance, any attack on a single member of the alliance can be successfully defended.ID: 030423421; System requirements: World Wide Web browser and PDF reader.; Mode of access: World Wide Web.; Thesis (Ph.D.)--University of Central Florida, 2011.; Includes bibliographical references (p. 206-210).
Ph.D.
Doctorate
Electrical Engineering and Computer Science
Engineering and Computer Science
26
Lachniet, Jason. "Alliance Partitions in Graphs." Digital Commons @ East Tennessee State University, 2007. https://dc.etsu.edu/etd/2080.
Full textAbstract:
For a graph G=(V,E), a nonempty subset S contained in V is called a defensive alliance if for each v in S, there are at least as many vertices from the closed neighborhood of v in S as in V-S. If there are strictly more vertices from the closed neighborhood of v in S as in V-S, then S is a strong defensive alliance. A (strong) defensive alliance is called global if it is also a dominating set of G. The alliance partition number (respectively, strong alliance partition number) is the maximum cardinality of a partition of V into defensive alliances (respectively, strong defensive alliances). The global (strong) alliance partition number is defined similarly. For each parameter we give both general bounds and exact values. Our major results include exact values for the alliance partition number of grid graphs and for the global alliance partition number of caterpillars.
27
Talon, Alexandre. "Intensive use of computing resources for dominations in grids and other combinatorial problems." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSEN079.
Full textAbstract:
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 18Our 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
28
Gledel, Valentin. "Couverture de sommets sous contraintes." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSE1130.
Full textAbstract:
Cette thèse porte sur le problème de la couverture d'ensembles finis dans une structure discrète. Cette problématique très générale permet de nombreuses approches et nous faisons l'étude de certaines d'entre elles. Le premier chapitre introduit les notions qui seront indispensables à la bonne compréhension de cette thèse et fait un bref état de l'art sur certains problèmes de couvertures, en particulier le problème de domination dans les graphes. Le second chapitre aborde la domination de puissance, une variante du problème de domination qui a la particularité qu'on lui adjoint un phénomène de propagation. Nous étudions ce problème pour les grilles triangulaires et les grilles carrées de dimension 3. Dans le troisième chapitre, nous revenons à la domination classique mais dans un contexte ludique, avec le jeu de domination Maker-Breaker. Nous étudions la complexité du problème consistant à décider quel joueur gagne, la durée minimale d'une partie si les deux joueurs jouent parfaitement, et dérivons ce jeu pour la domination totale et dans une version Avoider-Enforcer. Le quatrième chapitre traite du nombre géodésique fort, un problème qui a la particularité de se couvrir à l'aide de plus courts chemins dans le graphe. Nous étudions le nombre géodésique fort de plusieurs classes de graphes ainsi que son comportement en relation avec le produit cartésien. Enfin, dans le cinquième chapitre, nous quittons le domaine des graphes pour étudier l'identification de points dans le plan par des disques. En plus de couvrir chaque point d'un certain ensemble par des disques, nous souhaitons que l'ensemble des disques couvrants chaque point soit unique. Nous donnons des résultats dans certains cas particuliers, des bornes dans le cas général et étudions la complexité du problème quand le rayon des disques est fixéThis PhD thesis concerns the problem of covering finite sets in a discrete structure. This very general issue allows numerous approaches and we study some of them. The first chapter introduces the notions that are essentials to the understanding of this thesis and makes a brief state of the art on some covering problems, including the domination problem. The second chapter addresses the power dominating problem, a variation of the dominating problem with a propagation process. We study this problem on triangular grids and square grids of dimension 3. In the third chapter, we come back to the classical domination but in the context of a game, with the Maker-Breaker domination game. We study the complexity of the problem of deciding which player has a winning strategy and the minimum duration of a game if both players play perfectly. We also derive this problem for total domination and for an Avoider-Enforcer version. The fourth chapter is about the strong geodetic number: a problem with the distinctive characteristic that the covering is made by shortest paths in the graph. We study the strong geodetic number of several graph classes and its behaviour for the Cartesian product. Lastly, in the fifth chapter, we leave the realm of graphs to study the identification of points using disks. More than just covering every point of a certain set, the subset of disks covering each point must be unique to that point. We give results on particular configurations, bounds on the general case and we study the complexity of the problem when the radius of the disks is fixed
29
Grundlingh, Werner R. "Two new combinatorial problems involving dominating sets for lottery schemes." Thesis, Stellenbosch : University of Stellenbosch, 2004. http://hdl.handle.net/10019.1/1388.
Full textAbstract:
Thesis (PhD (Mathematical Sciences. Applied Mathematics))--University of Stellenbosch, 2004.Suppose a lottery scheme consists of randomly selecting an unordered winning n-subset from a universal set of m numbers, while a player participates in the scheme by purchasing a playing set of any number of unordered n-subsets from the same universal set prior to a winning draw, and is awarded a prize if ...
30
Parreau, Aline. "Problèmes d'identification dans les graphes." Phd thesis, Université de Grenoble, 2012. http://tel.archives-ouvertes.fr/tel-00745054.
Full textAbstract:
Dans cette thèse, nous étudions des problèmes d'identification des sommets dans les graphes. Identifier les sommets d'un graphe consiste à attribuer à chaque sommet un objet qui rend le sommet unique par rapport aux autres. Nous nous intéressons particulièrement aux codes identifiants : sous-ensembles de sommets d'un graphe, dominants, tels que le voisinage fermé de chaque sommet du graphe a une intersection unique avec l'ensemble. Les sommets du code identifiant peuvent être considérés comme des capteurs et chaque sommet du graphe comme un lieu possible pour une défaillance. Nous caractérisons tout d'abord l'ensemble des graphes pour lesquels tous les sommets sauf un sont nécessaires dans tout code identifiant. Le problème consistant à trouver un code identifiant optimal, c'est-'a-dire de taille minimale, étant NP-difficile, nous l'étudions sur quatre classes restreintes de graphes. Suivant les cas, nous pouvons résoudre complètement le problème (pour les graphes de Sierpinski), améliorer les bornes générales (pour les graphes d'intervalles, les graphes adjoints, la grille du roi) ou montrer que le problème reste difficile même restreint (pour les graphes adjoints). Nous considérons ensuite des variations autour des codes identifiants permettant plus de flexibilité pour les capteurs. Nous étudions par exemple des capteurs du plan capables de détecter des défaillances 'a un rayon connu avec une erreur tolérée. Nous donnons des constructions de tels codes et bornons leur taille pour des valeurs de rayons et d'erreurs fixés ou asymptotiques. Nous introduisons enfin la notion de coloration identifiante d'un graphe, permettant d'identifier les sommets d'un graphe avec les couleurs présentes dans son voisinage. Nous comparons cette coloration avec la coloration propre des graphes et donnons des bornes sur le nombre de couleurs nécessaires pour identifier un graphe, pour plusieurs classes de graphes.
31
Planche, Léo. "Décomposition de graphes en plus courts chemins et en cycles de faible excentricité." Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCB224.
Full textAbstract:
En collaboration avec des chercheurs en biologie à Jussieu, nous étudions des graphes issus de données biologiques afin de d'en améliorer la compréhension. Ces graphes sont constitués à partir de fragments d'ADN, nommés reads. Chaque read correspond à un sommet, et deux sommets sont reliés si les deux séquences d'ADN correspondantes ont un taux de similarité suffisant. Ainsi se forme des graphes ayant une structure bien particulière que nous nommons hub-laminaire. Un graphe est dit hub-laminaire s'il peut être résumé en quelques plus courts chemins dont tous les sommets du graphe soient proche. Nous étudions en détail le cas où le graphe est composé d'un unique plus court chemin d'excentricité faible, ce problème a été initialement défini par Dragan 2017. Nous améliorons la preuve d'un algorithme d'approximation déjà existant et en proposons un nouveau, effectuant une 3-approximation en temps linéaire. De plus, nous analysons le lien avec le problème de k-laminarité défini par Habib 2016, ce dernier consistant en la recherche d'un diamètre de faible excentricité. Nous étudions ensuite le problème du cycle isométrique de plus faible excentricité. Nous montrons que ce problème est NP-complet et proposons deux algorithmes d'approximations. Nous définissons ensuite précisément la structure "hub-laminaire" et présentons un algorithme d'approximation en temps O(nm). Nous confrontons cet algorithme à des graphes générés par une procédure aléatoire et l'appliquons à nos données biologiques. Pour finir nous montrons que le calcul du cycle isométrique d'excentricité minimale permet le plongement d'un graphe dans un cercle avec une distorsion multiplicative faible. Le calcul d'une décomposition hub-laminaire permet quant à lui une représentation compacte des distances avec une distorsion additive bornéeIn collaboration with reserchears in biology at Université Pierre et Marie Curie, we study graphs coming from biological data in order to improve our understanding of it. Those graphs come from DNA fragments, named reads. Each read is a vertex and two vertices are linked if the DNA sequences are similar enough. Such graphs have a particuliar structure that we name hub-laminar. A graph is said to be hub-laminar if it may be represented as a (small) set of shortest paths such that every vertex of the graph is close to one of those paths. We first study the case where the graph is composed of an unique shortest path of low eccentricity. This problem was first definied by Dragan 2017. We improve the proof of an approximation algorithm already existing and propose a new one, a 3-approximation running in linear time. Furthermore we show its link with the k-laminar problem defined by Habib 2016, consisting in finding a diameter of low eccentricity. We then define and study the problem of the isometric cycle of minimal eccentricity. We show that this problem is NP-complete and propose two approximation algorithms. We then properly define what is an hub-laminar decomposition and we show an approximation algorithm running in O(nm). We test this algorithm with randomly generated graphs and apply it to our biolgical data. Finaly we show that computing an isometric cycle of low eccentricity allows to embed a graph into a cycle with a low multiplicative distortion. Computing an hub-laminar decomposition allows a compact representation of distances with a low additive distortion
32
Cattaneo, David. "Modélisation graphique et simulation en traitement d'information quantique." Thesis, Université Grenoble Alpes (ComUE), 2017. http://www.theses.fr/2017GREAM076/document.
Full textAbstract:
Le formalisme des états graphes consiste à modéliser des états quantiques par des graphes. Ce formalisme permet l'utilisation des notions et des outils de théorie des graphes (e.g. flot, domination, méthodes probabilistes) dans le domaine du traitement de l'information quantique. Ces dernières années, cette modélisation combinatoire a permis plusieurs avancées décisives, notamment (i) dans la compréhension des propriétés de l'intrication quantique (ii) dans l'étude des modèles de calcul particulièrement prometteurs en terme d'implémentation physique, et (iii) dans l'analyse et la construction de protocoles de cryptographie quantique. L'objectif de cette thèse est d'étudier les propriétés graphiques émergeant des problématiques d'informatique quantique, notamment pour la simulation quantique. En particulier, l'étude des propriétés de causalité et de localité des états graphes, en étendant par exemple la notion existante de flot de causalité à une notion intégrant des contraintes de localité, permettrait d'ouvrir de nouvelles perspectives pour la simulation de systèmes quantiques à l'aide d'états graphes. Des connections formelles avec les automates cellulaires quantiques bruités pourront également émerger de cette étudeGraph States formalism consist in using graphs to model quantum states. This formalism allows us to use notion and tools of graph theory (e.g. flow, domination, probabilistic methods) in quantum information processing. Last years, this combinatorial modelisation had lead to many decisiv breakthroughs, in particular (i) in the comprehension of the quantum entranglement properties (ii) in very promising in term of physical implementation quantum calculus model, and (iii) in the analysis and construction of quantum cryptography protocols. The goal of this thesis is to study the graphic properties emerging of those quantum information processing problematics, especially for quantum simulation. In particular, the properties of causality and locality in graph states, by extanding for exemple the existing notion of causality flows to a notion integring the locality constraints, would allow new perspectives for the quantum system simulation using graphs states. Formal connections with noisy quantum cellular automata would emerge from this study
33
Muncy, David. "Automated Conjecturing Approach for Benzenoids." VCU Scholars Compass, 2016. http://scholarscompass.vcu.edu/etd/4608.
Full textAbstract:
Benzenoids are graphs representing the carbon structure of molecules, defined by a closed path in the hexagonal lattice. These compounds are of interest to chemists studying existing and potential carbon structures. The goal of this study is to conjecture and prove relations between graph theoretic properties among benzenoids. First, we generate conjectures on upper bounds for the domination number in benzenoids using invariant-defined functions. This work is an extension of the ideas to be presented in a forthcoming paper. Next, we generate conjectures using property-defined functions. As the title indicates, the conjectures we prove are not thought of on our own, rather generated by a process of automated conjecture-making. This program, named Cᴏɴᴊᴇᴄᴛᴜʀɪɴɢ, is developed by Craig Larson and Nico Van Cleemput.
34
Lang, Julie. "Graphs admitting (1, ≤ 2)-identifying codes." Thesis, Kansas State University, 2014. http://hdl.handle.net/2097/18260.
Full textAbstract:
Master of ScienceDepartment of Mathematics
Sarah Reznikoff
A (1, ≤ 2)-identifying code is a subset of the vertex set C of a graph such that each pair of vertices intersects C in a distinct way. This has useful applications in locating errors in multiprocessor networks and threat monitoring. At the time of writing, there is no simply-stated rule that will indicate if a graph is (1, ≤ 2)-identifiable. As such, we discuss properties that must be satisfied by a valid (1, ≤ 2)-identifying code, characteristics of a graph which preclude the existence of a (1, ≤ 2)-identifying code, and relationships between the maximum degree and order of (1, ≤ 2)-identifiable graphs. Additionally, we show that (1, ≤ 2)-identifiable graphs have no forbidden induced subgraphs and provide a list of (1, ≤ 2)-identifiable graphs with minimum (1, ≤ 2)-identifying codes indicated.
35
Camby, Eglantine. "Connecting hitting sets and hitting paths in graphs." Doctoral thesis, Universite Libre de Bruxelles, 2015. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/209048.
Full textAbstract:
Dans cette thèse, nous étudions les aspects structurels et algorithmiques de différents problèmes de théorie des graphes. Rappelons qu’un graphe est un ensemble de sommets éventuellement reliés par des arêtes. Deux sommets sont adjacents s’ils sont reliés par une arête.Tout d’abord, nous considérons les deux problèmes suivants :le problème de vertex cover et celui de dominating set, deux cas particuliers du problème de hitting set. Un vertex cover est un ensemble de sommets qui rencontrent toutes les arêtes alors qu’un dominating set est un ensemble X de sommets tel que chaque sommet n’appartenant pas à X est adjacent à un sommet de X. La version connexe de ces problèmes demande que les sommets choisis forment un sous-graphe connexe. Pour les deux problèmes précédents, nous examinons le prix de la connexité, défini comme étant le rapport entre la taille minimum d’un ensemble répondant à la version connexe du problème et celle d’un ensemble du problème originel. Nous prouvons la difficulté du calcul du prix de la connexité d’un graphe. Cependant, lorsqu’on exige que le prix de la connexité d’un graphe ainsi que de tous ses sous-graphes induits soit borné par une constante fixée, la situation change complètement. En effet, pour les problèmes de vertex cover et de dominating set, nous avons pu caractériser ces classes de graphes pour de petites constantes.
Ensuite, nous caractérisons en termes de dominating sets connexes les graphes Pk- free, graphes n’ayant pas de sous-graphes induits isomorphes à un chemin sur k sommets. Beaucoup de problèmes sur les graphes sont étudiés lorsqu’ils sont restreints à cette classe de graphes. De plus, nous appliquons cette caractérisation à la 2-coloration dans les hypergraphes. Pour certains hypergraphes, nous prouvons que ce problème peut être résolu en temps polynomial.
Finalement, nous travaillons sur le problème de Pk-hitting set. Un Pk-hitting set est un ensemble de sommets qui rencontrent tous les chemins sur k sommets. Nous développons un algorithme d’approximation avec un facteur de performance de 3. Notre algorithme, basé sur la méthode primal-dual, fournit un Pk-hitting set dont la taille est au plus 3 fois la taille minimum d’un Pk-hitting set.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished
36
Levy, Eythan. "Approximation algorithms for covering problems in dense graphs." Doctoral thesis, Universite Libre de Bruxelles, 2009. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210359.
Full textAbstract:
We present a set of approximation results for several covering problems in dense graphs. These results show that for several problems, classical algorithms with constant approximation ratios can be analyzed in a finer way, and provide better constant approximation ratios under some density constraints. In particular, we show that the maximal matching heuristic approximates VERTEX COVER (VC) and MINIMUM MAXIMAL MATCHING (MMM) with a constant ratio strictly smaller than 2 when the proportion of edges present in the graph (weak density) is at least 3/4, or when the normalized minimum degree (strong density) is at least 1/2. We also show that this result can be improved by a greedy algorithm which provides a constant ratio smaller than 2 when the weak density is at least 1/2. We also provide tight families of graphs for all these approximation ratios. We then looked at several algorithms from the literature for VC and SET COVER (SC). We present a unified and critical approach to the Karpinski/Zelikovsky, Imamura/Iwama and Bar-Yehuda/Kehat algorithms, identifying the general the general scheme underlying these algorithms.Finally, we look at the CONNECTED VERTEX COVER (CVC) problem,for which we proposed new approximation results in dense graphs. We first analyze Carla Savage's algorithm, then a new variant of the Karpinski-Zelikovsky algorithm. Our results show that these algorithms provide the same approximation ratios for CVC as the maximal matching heuristic and the Karpinski-Zelikovsky algorithm did for VC. We provide tight examples for the ratios guaranteed by both algorithms. We also introduce a new invariant, the "price of connectivity of VC", defined as the ratio between the optimal solutions of CVC and VC, and showed a nearly tight upper bound on its value as a function of the weak density. Our last chapter discusses software aspects, and presents the use of the GRAPHEDRON software in the framework of approximation algorithms, as well as our contributions to the development of this system.
/
Nous présentons un ensemble de résultats d'approximation pour plusieurs problèmes de couverture dans les graphes denses. Ces résultats montrent que pour plusieurs problèmes, des algorithmes classiques à facteur d'approximation constant peuvent être analysés de manière plus fine, et garantissent de meilleurs facteurs d'aproximation constants sous certaines contraintes de densité. Nous montrons en particulier que l'heuristique du matching maximal approxime les problèmes VERTEX COVER (VC) et MINIMUM MAXIMAL MATCHING (MMM) avec un facteur constant inférieur à 2 quand la proportion d'arêtes présentes dans le graphe (densité faible) est supérieure à 3/4 ou quand le degré minimum normalisé (densité forte) est supérieur à 1/2. Nous montrons également que ce résultat peut être amélioré par un algorithme de type GREEDY, qui fournit un facteur constant inférieur à 2 pour des densités faibles supérieures à 1/2. Nous donnons également des familles de graphes extrémaux pour nos facteurs d'approximation. Nous nous somme ensuite intéressés à plusieurs algorithmes de la littérature pour les problèmes VC et SET COVER (SC). Nous avons présenté une approche unifiée et critique des algorithmes de Karpinski-Zelikovsky, Imamura-Iwama, et Bar-Yehuda-Kehat, identifiant un schéma général dans lequel s'intègrent ces algorithmes.
Nous nous sommes finalement intéressés au problème CONNECTED VERTEX COVER (CVC), pour lequel nous avons proposé de nouveaux résultats d'approximation dans les graphes denses, au travers de l'algorithme de Carla Savage d'une part, et d'une nouvelle variante de l'algorithme de Karpinski-Zelikovsky d'autre part. Ces résultats montrent que nous pouvons obtenir pour CVC les mêmes facteurs d'approximation que ceux obtenus pour VC à l'aide de l'heuristique du matching maximal et de l'algorithme de Karpinski-Zelikovsky. Nous montrons également des familles de graphes extrémaux pour les ratios garantis par ces deux algorithmes. Nous avons également étudié un nouvel invariant, le coût de connectivité de VC, défini comme le rapport entre les solutions optimales de CVC et de VC, et montré une borne supérieure sur sa valeur en fonction de la densité faible. Notre dernier chapitre discute d'aspects logiciels, et présente l'utilisation du logiciel GRAPHEDRON dans le cadre des algorithmes d'approximation, ainsi que nos contributions au développement du logiciel.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished
37
Foucaud, Florent. "Aspects combinatoires et algorithmiques des codes identifiants dans les graphes." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2012. http://tel.archives-ouvertes.fr/tel-00766138.
Full textAbstract:
Nous étudions des aspects combinatoires et algorithmiques relatifs aux codes identifiants dans les graphes. Un code identifiant est un ensemble de sommets d'un graphe tel que, d'une part, chaque sommet hors du code a un voisin dans le code et, d'autre part, tous les sommets ont un voisinage distinct à l'intérieur du code. Nous caractérisons tout d'abord les graphes orientés et non-orientés atteignant les bornes supérieures connues pour la taille minimum d'un code identifiant. Nous donnons également de nouveaux majorants et minorants sur ce paramètre pour les graphes de degré maximum donné, les graphes de maille au moins 5, les graphes d'intervalles et les graphes adjoints. Nous étudions ensuite la complexité algorithmique des problèmes de décision et d'optimisation associés à la notion de code identifiant. Nous montrons que ces problèmes restent algorithmiquement difficiles, même quand on les restreint aux graphes bipartis, co-bipartis, split, d'intervalles ou adjoints. Enfin, nous donnons un algorithme PTAS pour les graphes d'intervalles unitaires.
38
Desormeaux, Wyatt Jules. "Total domination in graphs and graph modifications." Thesis, 2012. http://hdl.handle.net/10210/6158.
Full textAbstract:
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.
40
Marcon, Alister Justin. "Semitotal domination in graphs." Thesis, 2015. http://hdl.handle.net/10210/13867.
Full text
41
McCoy, John Patrick. "Paired-domination in graphs." Thesis, 2013. http://hdl.handle.net/10210/8556.
Full textAbstract:
D.Phil. (Mathematics)Domination and its variants are now well studied in graph theory. One of these variants, paired-domination, requires that the subgraph induced by the dominating set contains a perfect matching. In this thesis, we further investigate the concept of paired-domination. Chapters 2, 3, 4, and 5 of this thesis have been published in [17], [41], [42], and [43], respectively, while Chapter 6 is under submission; see [44]. In Chapter 1, we introduce the domination parameters we use, as well as the necessary graph theory terminology and notation. We combine the de nition of a paired-dominating set and a locating set to de ne three new sets: locating-paired- dominating sets, di erentiating-paired-dominating sets, and metric-locating-paired- dominating sets. We use these sets in Chapters 3 and 4. In Chapter 2, we investigate the relationship between the upper paired-domination and upper total domination numbers of a graph. In Chapter 3, we study the properties of the three kinds of locating paired-dominating sets we de ned, and in Chapter 4 we give a constructive characterisation of those trees which do not have a di erentiating- paired-dominating set. In Chapter 5, we study the problem of characterising planar graphs with diameter two and paired-domination number four. Lastly, in Chap- ter 6, we establish an upper bound on the size of a graph of given order and paired- domination number and we characterise the extremal graphs that achieve equality in the established bound.
42
"Stratification and domination in graphs." Thesis, 2006. http://hdl.handle.net/10413/1891.
Full textAbstract:
In a recent manuscript (Stratification and domination in graphs. Discrete Math. 272 (2003), 171-185) a new mathematical framework for studying domination is presented. It is shown that the domination number and many domination related parameters can be interpreted as restricted 2-stratifications or 2-colorings. This framework places the domination number in a new perspective and suggests many other parameters of a graph which are related in some way to the domination number. In this thesis, we continue this study of domination and stratification in graphs. Let F be a 2-stratified graph with one fixed blue vertex v specified. We say that F is rooted at the blue vertex v. An F-coloring of a graph G is a red-blue coloring of the vertices of G such that every blue vertex v of G belongs to a copy of F (not necessarily induced in G) rooted at v. The F-domination number yF(GQ of G is the minimum number of red vertices of G in an F-coloring of G. Chapter 1 is an introduction to the chapters that follow. In Chapter 2, we investigate the X-domination number of prisms when X is a 2-stratified 4-cycle rooted at a blue vertex where a prism is the cartesian product Cn x K2, n > 3, of a cycle Cn and a K2. In Chapter 3 we investigate the F-domination number when (i) F is a 2-stratified path P3 on three vertices rooted at a blue vertex which is an end-vertex of the F3 and is adjacent to a blue vertex and with the remaining vertex colored red. In particular, we show that for a tree of diameter at least three this parameter is at most two-thirds its order and we characterize the trees attaining this bound. (ii) We also investigate the F-domination number when F is a 2-stratified K3 rooted at a blue vertex and with exactly one red vertex. We show that if G is a connected graph of order n in which every edge is in a triangle, then for n sufficiently large this parameter is at most (n — /n)/2 and this bound is sharp. In Chapter 4, we further investigate the F-domination number when F is a 2- stratified path P3 on three vertices rooted at a blue vertex which is an end-vertex of the P3 and is adjacent to a blue vertex with the remaining vertex colored red. We show that for a connected graph of order n with minimum degree at least two this parameter is bounded above by (n —1)/2 with the exception of five graphs (one each of orders four, five and six and two of order eight). For n > 9, we characterize those graphs that achieve the upper bound of (n — l)/2. In Chapter 5, we define an f-coloring of a graph to be a red-blue coloring of the vertices such that every blue vertex is adjacent to a blue vertex and to a red vertex, with the red vertex itself adjacent to some other red vertex. The f-domination number yz{G) of a graph G is the minimum number of red vertices of G in an f-coloring of G. Let G be a connected graph of order n > 4 with minimum degree at least 2. We prove that (i) if G has maximum degree A where A 4 with maximum degree A where A 5 with maximum degree A where 3Thesis (Ph.D.)-University of KwaZulu-Natal, Pietermaritzburg, 2006.
43
Joubert, Ernest. "Aspects of total restrained domination in graphs." Thesis, 2009. http://hdl.handle.net/10210/2354.
Full text
44
Schurch, Mark. "Domination parameters of prisms of graphs." 2005. http://hdl.handle.net/1828/825.
Full text
45
Yang, Feiran. "New results on broadcast domination and multipacking." Thesis, 2015. http://hdl.handle.net/1828/6627.
Full textAbstract:
Let G be a graph and f be a function that maps V to {0,1,2, ..., diam(G)}.
Let V+ be the set of all vertices such that f(v) is positive.
If for every vertex v not in V+ there exists a vertex w in V+ such that
the distance between v and w is at most f(w),
then f is called a dominating broadcast of G.
The cost of the broadcast f is the sum of the values f(v) over all vertices v in V.
The minimum cost of a dominating broadcast is called the broadcast domination number of G.
A subset S of V is a multipacking if, for every v in V and for every integer k which is at least 1 and at most rad(G),
the set S contains at most k vertices at distance at most k from v.
The multipacking number of G is the maximum cardinality of a multipacking of G.
In the first part of the thesis, we describe how linear programming can be used to give a cubic algorithm to find the broadcast domination number and multipacking number of strongly chordal graphs.
Next, we restrict attention to trees, and describe linear time algorithms to compute these numbers. Finally, we introduce k-broadcast domination and k-multipacking, develop the basic theory and give a bound for the 2-broadcast domination number of a tree in terms of its order.Graduate
46
Edwards, Michelle. "Vertex-Criticality and Bicriticality for Independent Domination and Total Domination in Graphs." Thesis, 2015. http://hdl.handle.net/1828/6097.
Full textAbstract:
For any graph parameter, the removal of a vertex from a graph can increase the parameter, decrease the parameter, or leave the parameter unchanged. This dissertation focuses on the case where the removal of a vertex decreases the parameter for the cases of independent domination and total domination. A graph is said to be independent domination vertex-critical, or i-critical, if the removal of any vertex decreases the independent domination number. Likewise, a graph is said to be total domination vertex-critical if the removal of any vertex decreases the total domination number. Following these notions, a graph is independent domination bicritical, or i-bicritical, if the removal of any two vertices decreases the independent domination number, and a graph is total domination bicritical if the removal of any two vertices decreases the total domination number. Additionally, a graph is called strong independent domination bicritical, or strong i-bicritical, if the removal of any two independent vertices decreases the independent domination number by two.
Construction results for i-critical graphs, i-bicritical graphs, strong i-bicritical graphs, total domination critical graphs, and total domination bicritical graphs are studied. Many known constructions are extended to provide necessary and sufficient conditions to build critical and bicritical graphs. New constructions are also presented, with a concentration on i-critical graphs. One particular construction shows that for any graph G, there exists an i-critical, i-bicritical, and strong i-bicritical graph H such that G is an induced subgraph of H. Structural properties of i-critical graphs, i-bicritical graphs, total domination critical graphs, and total domination bicritical graphs are investigated, particularly for the connectedness and edge-connectedness of critical and bicritical graphs. The coalescence construction, which has appeared in earlier literature, constructs a graph with a cut-vertex and this construction is studied in great detail for i-critical graphs, i-bicritical graphs, total domination critical graphs, and total domination bicritical graphs. It is also shown that strong i-bicritical graphs are 2-connected and thus the coalescence construction is not useful in this case.
Domination vertex-critical graphs (graphs where the removal of any vertex decreases the domination number) have been studied in the literature. A well-known result gives an upper bound on the diameter of such graphs. Here similar techniques are used to provide upper bounds on the diameter for i-critical graphs, strong i-bicritical graphs, and total domination critical graphs. The upper bound for the diameter of i-critical graphs trivially gives an upper bound for the diameter of i-bicritical graphs.
For a graph G, the gamma-graph of G is the graph where the vertex set is the collection of minimum dominating sets of G. Adjacency between two minimum dominating sets in the gamma-graph occurs if from one minimum dominating set a vertex can be removed and replaced with a vertex to arrive at the other minimum dominating set. One can think of adjacency between minimum dominating sets in the gamma-graph as a swap of two vertices between minimum dominating sets. In the single vertex replacement adjacency model these two vertices can be any vertices in the minimum dominating sets, and in the slide adjacency model these two vertices must be adjacent in G. (Hence the gamma-graph obtained from the slide adjacency model is a subgraph of the gamma-graph obtained in the single vertex replacement adjacency model.) Results for both adjacency models are presented concerning the maximum degree, the diameter, and the order of the gamma-graph when G is a tree.Graduate
0405
michaedwards@gmail.com
47
Dorfling, Samantha. "Domination in graphs with bounded degrees." Thesis, 2012. http://hdl.handle.net/10210/7284.
Full textAbstract:
M.Sc.Let G be a graph and D a set of vertices such that every vertex in G is in D or adjacent to at least one vertex in D. Then D is called a dominating set of G and the smallest cardinality of such a dominating set of G is known as the domination number of G, denoted by y(G). This short dissertation is a study of the domination number in graphs with bounds on both the minimum and maximum degrees. In Chapter 1 we give all definitions, terminology and references related to the material presented in this thesis. In Chapter 2 we study an article by McCuaig and Shepherd which considers graphs with minimum degree two and gives an upper bound for their domination numbers in terms of their order. This bound is also an improvement of one originally determined by Ore. In Chapter 3 an article by Fisher, Fraughnaugh and Seager is studied. Here the domination number in graphs with maximum degree at most three is discussed. Furthermore au upper bound on the domination number of a graph is given in terms of its order, size and the number of isolated vertices it contains. This result is an extension of a previous result by Reed on domination in graphs with minimum degree three. A set U of vertices of a graph G = (V, E) is k-dominating if each vertex of V — U is adjacent to at least k vertices of U. The k-domination number of G, Yk (G), is the smallest cardinality of a k-dominating set of G. Finally in Chapter 4 we study an article by Cockayne, Gamble and Shepherd which gives an upper bound for the k-domination number of a graph with minimum degree at least k. This result is a generalization of a result by Ore.
48
Finbow, Stephen. "Generalisations of irredundance in graphs." Thesis, 2003. http://hdl.handle.net/1828/7913.
Full textAbstract:
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
49
Smithdorf, Vivienne. "Aspects of distance and domination in graphs." Thesis, 1995. http://hdl.handle.net/10413/5142.
Full textAbstract:
The first half of this thesis deals with an aspect of domination; more specifically, we
investigate the vertex integrity of n-distance-domination in a graph, i.e., the extent
to which n-distance-domination properties of a graph are preserved by the deletion
of vertices, as well as the following: Let G be a connected graph of order p and let
oi- S s;:; V(G). An S-n-distance-dominating set in G is a set D s;:; V(G) such that
each vertex in S is n-distance-dominated by a vertex in D. The size of a smallest
S-n-dominating set in G is denoted by I'n(S, G). If S satisfies I'n(S, G) = I'n(G),
then S is called an n-distance-domination-forcing set of G, and the cardinality of a
smallest n-distance-domination-forcing set of G is denoted by On(G). We investigate
the value of On(G) for various graphs G, and we characterize graphs G for which
On(G) achieves its lowest value, namely, I'n(G), and, for n = 1, its highest value,
namely, p(G). A corresponding parameter, 1](G), defined by replacing the concept
of n-distance-domination of vertices (above) by the concept of the covering of edges
is also investigated.
For k E {a, 1, ... ,rad(G)}, the set S is said to be a k-radius-forcing set if, for each
v E V(G), there exists Vi E S with dG(v, Vi) ~ k. The cardinality of a smallest
k-radius-forcing set of G is called the k-radius-forcing number of G and is denoted
by Pk(G). We investigate the value of Prad(G) for various classes of graphs G,
and we characterize graphs G for which Prad(G) and Pk(G) achieve specified values.
We show that the problem of determining Pk(G) is NP-complete, study the
sequences (Po(G),Pl(G),P2(G), ... ,Prad(G)(G)), and we investigate the relationship
between Prad(G)(G) and Prad(G)(G + e), and between Prad(G)(G + e) and the connectivity
of G, for an edge e of the complement of G.
Finally, we characterize integral triples representing realizable values of the triples
b,i,p), b,l't,i), b,l'c,p), b,l't,p) and b,l't,l'c) for a graph.Thesis (Ph.D.-Mathematics and Applied Mathematics)-University of Natal, 1995.
50
Smithdorf, Vivienne. "On the integrity of domination in graphs." Thesis, 1993. http://hdl.handle.net/10413/8098.
Full textAbstract:
This thesis deals with an investigation of the integrity of domination in a.graph, i.e., the extent to
which domination properties of a graph are preserved if the graph is altered by the deletion of
vertices or edges or by the insertion of new edges.
A brief historical introduction and motivation are provided in Chapter 1. Chapter 2 deals with kedge-(
domination-)critical graphs, i.e., graphsG such that )'(G) = k and )'(G+e) < k for all e E
E(G). We explore fundamental properties of such graphs and their characterization for small
values of k. Particular attention is devoted to 3-edge-critical graphs.
In Chapter 3, the changes in domination number brought aboutby vertex removal are investigated.
\
Parameters )'+'(G) (and "((G)), denoting the smallest number of vertices of G in a set 5 such that
)'(G-5) > )'(G) ()'(G -5) < )'(G), respectively), are investigated, as are'k-vertex-critical graphs G
(with )'(G) = k and )'(G-v) < k for all v E V(O)). The existence of smallest'domination-forcing
sets of vertices of graphs is considered.
The bondage number 'Y+'(G), i.e., the smallest number of edges of a graph G in a set F such that
)'(G- F) > )'(0), is investigated in Chapter 4, as are associated extremal graphs. Graphs with
dominating sets or domination numbers that are insensitive to the removal of an arbitrary edge are
considered, with particular reference to such graphs of minimum size.
Finally, in Chapter 5, we-discuss n-dominating setsD of a graph G (such that each vertex in G-D
is adjacent to at least n vertices in D) and associated parameters. All chapters but the first and
fourth contain a listing of unsolved problems and conjectures.Thesis (M.Sc.)-University of Natal, 1993.