Given a digraph D = (V, A), with vertex set V and arc set A, a set S ⊆ V is a dominating set if for every vertex v in V \ S, there are a vertex u in S and an arc (u, v) from u to v. In this chapter we consider the counterparts in directed graphs of independent, dominating, independent dominating, and total dominating sets in undirected graphs.

This paper presents the G-network, a new topological design which is a suitable architecture for point-to-point communication and interconnection networks, We show that the G-network has the following desirable characteristics: Efficient routing, small number of links, and fault tolerance. The performance of the G-network is compared to that of the Barrel Shifter and Illiac Mesh networks.

A set S of vertices in a graph G is a paired dominating set if every vertex of G is adjacent to a vertex in S and the subgraph induced by S contains a perfect matching (not necessarily as an induced subgraph). The minimum cardinality of a paired dominating set of G is the paired domination number of G. This chapter presents a survey of the major results on paired domination with an emphasis on bounds for the paired domination number.

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.

Thesis--Auburn University, 2008. / Abstract. Vita. Includes bibliographical references (p. 45-48).

Understanding RNA molecules is important to genomics research. Recently researchers at the Courant Institute of Mathematical Sciences used graph theory to model RNA molecules and provided a database of trees representing possible secondary RNA structures. In this thesis we use domination parameters to predict which trees are more likely to exist in nature as RNA structures. This approach appears to have promise in graph theory applications in genomics research.

No description available.

No description available.

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.

Wireless sensor networks (WSNs) are now widely used in many applications. Connected Dominating Set (CDS) based routing which is one kind of hierarchical methods has received more attention to reduce routing overhead. The concept of k-connected m-dominating sets (kmCDS) is used to provide fault tolerance and routing flexibility. In this thesis, we first consider how to construct a CDS in WSNs. After that, centralized and distributed algorithms are proposed to construct a kmCDS. Moreover, we introduce some basic ideas of how to use CDS in other potential applications such as partial coverage and data dissemination in WSNs.