Given a graph with domination number γ, we find bounds on the maximum number of minimum dominating sets. First, for γ≥3, we obtain lower bounds on the number of γ-sets that do not dominate a graph on n vertices. Then, we show that γ-fold lexicographic product of the complete graph on n1/γ vertices has domination number γ and γn-O(nγ-γ/1) dominating sets of size γ. Finally, we see that a certain random graph has, with high probability, (i) domination number γ; and (ii) all but o(nγ) of its γ-sets being dominating.

Master of Science / Department 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.

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

A coalition in a graph (Formula presented.) consists of two disjoint sets of vertices V 1 and V 2, neither of which is a dominating set but whose union (Formula presented.) is a dominating set. A coalition partition in a graph G of order (Formula presented.) is a vertex partition (Formula presented.) such that every set Vi of π either is a dominating set consisting of a single vertex of degree n–1, or is not a dominating set but forms a coalition with another set (Formula presented.) which is not a dominating set. In this paper we introduce this concept and study its properties.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-08-12T15:13:32Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) dissertacao rommel cc.pdf: 1665635 bytes, checksum: 9f894f847272036c011387e2de71507f (MD5) / Made available in DSpace on 2014-08-12T15:13:32Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) dissertacao rommel cc.pdf: 1665635 bytes, checksum: 9f894f847272036c011387e2de71507f (MD5) Previous issue date: 2009-03-12 / Given a graph G = (V;E) and a set of vertices D V, a vertice v 2 V is dominated by D if jN[v] \ Dj 1. When jN(v) \ Dj = 1 for all v 2 V, G is efficiently dominable. A generalization of this concept is called efficient multiple domination, which requires all vertices must be dominated by a set D V exactly k times. The aim of this dissertation is to study these topics, describing the theoretical knowledge needed for advanced researches. For this reason, many of the theorems and its proofs are detailed. Furthermore, some results on the efficient multiple domination are presented, including bounds for the size of efficient k-dominating sets, the complement and iterated line graphs of efficiently (r + 1)-dominable r-regular graphs and a N P-completeness proof for the efficient multiple domination problem in arbitrary graphs. It is expected that this work contribute to the development of future researches on the efficient domination and in the resolution of some open problems. / Dado um grafo G = (V;E) e um subconjunto de vértices D V, define-se D como um conjunto dominante de G se todo vértice v 2 V que não estiver incluído no conjunto D for adjacente a pelo menos um vértice de D. Na situação em que, para todo v 2 V, jN[v]\Dj = 1, diz-se que o grafo G é eficientemente dominado. Uma generalização desse conceito consiste na múltipla dominação eficiente, em que é requerido que todo vértice do grafo seja dominado exatamente k vezes. O objetivo deste trabalho é realizar um estudo exploratório sobre esses temas, de modo a reunir o conhecimento teórico requerido para pesquisas avançadas. Para isso, buscou-se a apresentação e o detalhamento das demonstrações dos teoremas estudados. Além disso, foram fornecidos alguns resultados sobre a múltipla dominação eficiente no que se refere aos limites para o tamanho de um conjunto k-dominante eficiente, à relação da k-dominação eficiente entre grafos regulares, seu complemento e seus grafos linha iterados, bem como à caracterização da N P-completude para o problema da múltipla dominação eficiente em grafos arbitrários. Espera-se que esta dissertação forneça subsídios teóricos para estudos futuros voltados à dominação eficiente, bem como à resolução de algumas questões em aberto.

The objective of this dissertation is to study commonly occurring location and clustering problems on graphs. The dissertation is presented as a collection of results in topics including finding maximum cliques in large graphs, graph clustering in large scale graphs, determining location of facilities for pre-positioning emergency relief supplies, and selecting nodes to form a virtual backbone in a wireless sensor network. To begin with, a new clique relaxation called a k-community is defined as a connected subgraph such that endpoints of every edge have at least k common neighbors within the subgraph. It is used to develop scale reduction techniques to obtain the maximum clique on very large scale real life networks. Analytically, the technique is been shown to be very effective on power-law random graphs. Experimental results on real life graph instances (Collaboration networks, P2P networks, Social networks, etc.) show our procedure to be much more effective than a regular k-core peeling approach. Next, a general purpose network clustering algorithm based on the clique relaxation concept of k-community is presented. A salient feature of this approach is that it does not use any prior information about the structure of the network. By defining a cluster as a k-community, the proposed algorithm aims to provide a clustering of a network into k-communities with varying values of k. Even though the algorithm is not designed to optimize any particular performance measure, the computational results suggest that it performs well on a number of criteria that are used in literature to evaluate the quality of a clustering. The third topic deals with choosing the locations of disaster response facilities for the storage of emergency supplies, which is critical to the quality of service provided in a large scale emergency like an earthquake. In the existing literature, large scale emergency facility location models have either assumed that disaster response facilities will always be functioning and available when required, or that the functioning of a facility is independent of a particular disaster scenario. In this paper new location models are presented that explicitly take into consideration the stochastic nature of the impact a disaster can have on the disaster response facilities and the population centers in surrounding areas. A comparison of the results obtained using our models with those from models available in literature using a case study suggests that the locations suggested by the model in this paper significantly reduce the expected cost of transportation of supplies when we consider the damage a disaster causes to the disaster response facilities and areas near it. Lastly, a distributed approximate algorithm for forming the communication backbone in wireless sensor networks is presented. Some of the most popular routing protocols for wireless sensor networks require a virtual backbone for efficient communication be- tween the sensors. Connected Dominating Sets (CDS) have been studied as a method of choosing nodes to be in the backbone. The traditional approach is to assume that the transmission range of each node is given and then minimize the number of nodes in the CDS representing the backbone. A recently introduced alternative strategy is based on the concept of k-bottleneck connected dominating set (k-BCDS), which, given a positive integer k, minimizes the transmission range of the nodes that ensures a CDS of size k exists in the network. This paper provides a 6-approximate distributed algorithm for the k-BCDS problem. The results of empirical evaluation of the proposed algorithm are also included.

For a graph G, the minimum dominating set problem is to find a minimum size set S of vertices of G such that every vertex is either in S or adjacent to a vertex in the set. The decision version of this problem, which asks whether G has a dominating set of a particular size k, is known to be NP-complete, and no polynomial time algorithm to solve the problem is currently known to exist. The queen domination problem is to find the minimum number of queens which, collectively, can attack every square on an n by n chess board. The related border queen problem is to find such a collection of queens with the added restriction that all queens lie on the outer border of the board. This thesis studies practical exponential time algorithms for solving domination problems, and presents an experimental comparison of several different algorithms, with the goal of producing a broadly effective general domination solver for use by future researchers. The developed algorithms are then used to solve several open problems, including cases of the queen domination problem and the border queen problem. In addition, new theoretical upper bounds are presented for the border queen problem for some families of queen graphs. / Graduate

A total dominating set in a graph G is a set S of vertices of G such that every vertex in G is adjacent to a vertex of S. We study graphs whose vertex set can be partitioned into two total dominating sets. In particular, we develop several sufficient conditions for a graph to have a vertex partition into two total dominating sets. We also show that with the exception of the cycle on five vertices, every selfcomplementary graph with minimum degree at least two has such a partition.

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

Wavelength division multiplexed (WDM) optical networks are rapidly becoming the technology of choice in network infrastructure and next-generation Internet architectures. WDM networks have the potential to provide unprecedented bandwidth, reduce processing cost, achieve protocol transparency, and enable efficient failure handling. This dissertation addresses the important issues of improving the performance and enhancing the reliability of WDM networks as well as modeling and evaluating the performance of these networks. Optical wavelength conversion is one of the emerging WDM enabling technologies that can significantly improve bandwidth utilization in optical networks. A new approach for the sparse placement of full wavelength converters based on the concept of the k-Dominating Set (k-DS) of a graph is presented. The k-DS approach is also extended to the case of limited conversion capability using three scalable and cost-effective switch designs: flexible node-sharing, strict node-sharing and static mapping. Compared to full search algorithms previously proposed in the literature, the K-DS approach has better blocking performance, has better time complexity and avoids the local minimum problem. The performance benefit of the K-DS approach is demonstrated by extensive simulation. Fiber delay line (FDL) is another emerging WDM technology that can be used to obtain limited optical buffering capability. A placement algorithm, k-WDS, for the sparse placement of FDLs at a set of selected nodes in Optical Burst Switching (OBS) networks is proposed. The algorithm can handle both uniform and non-uniform traffic patterns. Extensive performance tests have shown that k-WDS provides more efficient placement of optical fiber delay lines than the well-known approach of placing the resources at nodes with the highest experienced burst loss. Performance results that compare the benefit of using FDLs versus using optical wavelength converters (OWCs) are presented. A new algorithm, A-WDS, for the placement of an arbitrary numbers of FDLs and OWCs is introduced and is evaluated under different non-uniform traffic loads. This dissertation also introduces a new cost-effective optical switch design using FDL and a QoS-enhanced JET (just enough time) protocol suitable for optical burst switched WDM networks. The enhanced JET protocol allows classes of traffic to benefit from FDLs and OWCs while minimizing the end-to-end delay for high priority bursts. Performance evaluation models of WDM networks represent an important research area that has received increased attention. A new analytical model that captures link dependencies in all-optical WDM networks under uniform traffic is presented. The model enables the estimation of connection blocking probabilities more accurately than previously possible. The basic formula of the dependency between two links in this model reflects their degree of adjacency, the degree of connectivity of the nodes composing them and their carried traffic. The usefulness of the model is illustrated by applying it to the sparse wavelength converters placement problem in WDM networks. A lightpath containing converters is divided into smaller sub-paths such that each sub-path is a wavelength continuous path and the nodes shared between these sub-paths are full wavelength conversion capable. The blocking probability of the entire path is obtained by computing the blocking probabilities of the individual sub-paths. The analytical-based sparse placement algorithm is validated by comparing it with its simulation-based counterpart using a number of network topologies. Rapid recovery from failure and high levels of reliability are extremely important in WDM networks. A new Fault Tolerant Path Protection scheme, FTPP, for WDM mesh networks based on the alarming state of network nodes and links is introduced. The results of extensive simulation tests show that FTPP outperforms known path protection schemes in terms of loss of service ratio and network throughput. The simulation tests used a wide range of values for the load intensity, the failure arrival rate and the failure holding time. The FTPP scheme is next extended to the differentiated services model and its connection blocking performance is evaluated. Finally, a QoS-enhanced FTPP (QEFTPP) routing and path protection scheme in WDM networks is presented. QEFTPP uses preemption to minimize the connection blocking percentage for high priority traffic. Extensive simulation results have shown that QEFTPP achieves a clear QoS differentiation among the traffic classes and provides a good overall network performance.