Orientador: Christiane Neme CamposDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: Um conjunto dominante em um grafo $G = (V(G), E(G))$ é um conjunto $S \subseteq V(G)$, tal que todo vértice do grafo, ou pertence a $S$, ou é adjacente a pelo menos um elemento de $S$. O \emph{problema do conjunto dominante} consiste em determinar a cardinalidade de um conjunto dominante mínimo em um grafo $G$. Muitas aplicações podem ser modeladas como problemas de conjuntos dominantes e algumas delas levaram ao surgimento de variantes do problema original. O \emph{problema da clique-dominante} consiste em determinar a cardinalidade de um conjunto clique-dominante mínimo em um grafo $G$. Um \emph{conjunto clique-dominante} é um conjunto dominante que tem a propriedade adicional de ser uma clique. Em 1977, Cockayne e Hedetniemi definiram uma \emph{partição dominante} de um grafo $G = (V(G), E(G))$ como uma partição de $V(G)$ em conjuntos dominantes. O \emph{problema da partição dominante} consiste em determinar a cardinalidade máxima de uma partição dominante. Uma extensão natural deste problema consiste em considerar partições de $V(G)$ em conjuntos dominantes com propriedades adicionais. Em particular, o \emph{problema da partição em cliques-dominantes} consiste em determinar, caso exista, a cardinalidade máxima de uma partição de $V(G)$, tal que cada uma de suas partes seja um conjunto clique-dominante em $G$. O \emph{número clique-domático} de um grafo $G$ é definido como $d_{cl}(G) := \max\{|\mathscr{P}| : \mathscr{P}$ é uma partição de $V(G)$ em cliques-dominantes$\}$. Esta dissertação, aborda o problema da clique-dominante e o problema da partição em cliques-dominantes. São estudadas as origens destes dois problemas e alguns dos resultados existentes na literatura. Para o problema da clique-dominante é formulada uma conjetura que estabelece uma condição suficiente para um grafo possuir uma clique-dominante. No problema da partição em cliques-dominantes são exibidos resultados para algumas classes de grafos. Em particular, são caracterizados os grafos bipartidos e as potências de ciclos que possuem partição em cliques-dominantes e para estes grafos o número clique-domático é determinado. Resultados semelhantes também são apresentados para a classe dos grafos obtidos por meio da operação de produto cartesiano e para os grafos obtidos por meio do produto direto de grafos completosAbstract: A dominating set of a graph $G = (V(G), E(G))$ is a set $S \subseteq V(G)$ such that every vertex of $G$ belongs to $S$ or is adjacent to at least one vertex in $S$. The \emph{dominating set problem} consists of determining the minimum number of vertices in a dominating set of $G$. Many real-world applications can be modelled as dominating set problems and some of then led to the appearance of variants of the original problem. A \emph{dominating clique set} is a dominating set that is also a clique. The \emph{dominating clique problem} consists of determining the minimum number of vertices in a dominating clique set of a graph $G$. In 1977, Cockayne and Hedetniemi defined a \emph{domatic partition} of a graph $G = (V(G), E(G))$ as a partition of $V(G)$ in dominating sets. The \emph{domatic partition problem} consists of determining the maximum number of parts in a domatic partition of a graph. A natural extension of this problem consists of considering partitions of $V(G)$ in dominating sets with aditional properties. In particular, a \emph{clique domatic partition} is a partition of $V(G)$ into dominating clique sets; and the \emph{clique domatic partition problem}, the problem of determining the \emph{clique domatic number} of $G$, $d_{cl}(G) := \max\{|\mathscr{P}| : \mathscr{P}$ is a clique domatic partition of $G\}$, when $G$ has at least one clique domatic partition. In this work, we approach the dominating clique problem and the clique domatic partition problem. For the dominating clique problem we review some existing results in the literature and formulate a conjecture, which establishes a sufficient condition for the existence of a dominating clique set in a graph. On the clique domatic partition problem, we obtained results in some classes of graphs. In particular, we characterize the bipartite graphs and powers of cycles which have clique domatic partitions and for these graphs we determine the clique domatic number. Similar results are also obtained for the class of graphs generated by the cartesian product operation and the class of graphs generated by the direct product of complete graphsMestradoCiência da ComputaçãoMestre em Ciência da Computação