Search

The dominating set of the graph G is a subset D of vertex set V, such that every vertex not in V -- D is adjacent to at least one vertex in the vertex subset D. A dominating set D is a minimal dominating set if no proper subset of D is a dominating set. The number of elements in such set is called as domination number of graph and is denoted by (G). In this work the domination numbers are obtained for family of prism graphs such as prism CLn, antiprism Qn and crossed prism Rn by identifying one of their minimum dominating set. [ABSTRACT FROM AUTHOR]

A graph G is super strongly perfect if every induced subgraph H of G possesses a minimal dominating set meeting all the maximal cliques of H. Different structural properties of super strongly perfect graphs are studied in this paper. Some of the special categories of super strongly perfect graphs are identified and characterized. Certain operations of super strongly perfect graphs are also discussed towards the end. [ABSTRACT FROM AUTHOR]

We show that all minimal dominating sets of a chordal bipartite graph can be generated in incremental polynomial, hence output polynomial, time. Enumeration of minimal dominating sets in graphs is equivalent to enumeration of minimal transversals in hypergraphs. Whether the minimal transversals of a hypergraph can be enumerated in output polynomial time is a well-studied and challenging question that has been open for several decades. With this result we contribute to the known cases having an affirmative reply to this important question. [ABSTRACT FROM AUTHOR]

In a graph or a network , a set is a dominating set if each node in is adjacent to at least one node in . A dominating set is called minimal when there does not exist a node such that the set is a dominating set. In this paper, we propose a new self-stabilizing algorithm for minimal dominating set. It has safe convergence property under synchronous daemon in the sense that starting from an arbitrary state, it quickly converges to a dominating set (a safe state) in two rounds, and then stabilizes in a minimal dominating set (the legitimate state) in rounds without breaking safety during the convergence interval, where n is the number of nodes. Space requirement at each node is bits. [ABSTRACT FROM AUTHOR]

A theorem of Ore [20] states that if D is a minimal dominating set in a graph G = ( V , E ) having no isolated nodes, then V − D is a dominating set. It follows that such graphs must have two disjoint minimal dominating sets R and B . We describe a self-stabilizing algorithm for finding such a pair of sets. It also follows from Ore's theorem that in a graph with no isolates, one can find disjoint sets R and B where R is maximal independent and B is minimal dominating. We describe a self-stabilizing algorithm for finding such a pair. Both algorithms are described using the Distance-2 model, but can be converted to the usual Distance-1 model [7] , yielding running times of O ( n 2 m ) . [ABSTRACT FROM AUTHOR]

Let G = (V,E) be a graph. When G is used to model the network of a group of individuals, the vertex set V stands for individuals and the edge set E is used to represent the relations between them. If we want a set of representatives having relations with other members of the group, choose a dominating set of the graph. For a smallest set of representatives, choose a minimal dominating set of the graph. In this paper we generalize this concept by allowing the division of the group into a number of subgroups. We introduce the concept of class domination (greed domination) and study it's properties. A dominating set S of G is a class dominating set or a greed dominating set, if S ȩ Vi ≠ θ for all i. Here Vi such that i = 1, 2, …, n is a partition of V . We also discuss different versions of domination in the context of social networks. [ABSTRACT FROM AUTHOR]