Search

Claude Berge (1987) introduced the concept of k-extendable graphs, wherein any independent set of size k is inherently a constituent of a maximum independent set within a graph H = (V , E) . Graphs possessing the property of being 1-extendable are termedas Berge graphs. This introduction gave rise to the notion of well-covered graphs and well-dominated graphs. A graph is categorized as well-covered if each of its maximal independent sets is, in fact, a maximum independent set. Similarly, a graph attains the classification of well-dominated if every minimal dominating set (DS) within it is a minimum dominating set. In alignment with the concept of k-extendable graphs, the framework of (k , γ) -endowed graphs and symmetric (k , γ) -endowed graphs are established. In these graphs, each DS of size k encompasses a minimum DS of the graph. In this article, a study of γ -endowed dominating sets is initiated. Various results providing a deep insight into γ -endowed dominating sets in graphs such as those characterizing the ones possessing a unique minimum DS are proven. We also introduce and study the symmetric γ -endowed graphs and minimality of dominating sets in them. In addition, we give a solution to an open problem in the literature. which seeks to find a domination-based parameter that has a correlation coefficient of ρ > 0.9967 with the total π -electronic energy of lower benzenoid hydrocarbons. We show that the upper dominating number Γ (H) studied in this paper delivers a strong prediction potential. [ABSTRACT FROM AUTHOR]

This study devises self-stabilizing algorithms that leverage the expression distance-2 paradigm to compute (i) a maximal distance-2 independent set, wherein selected nodes maintain a separation exceeding two edges, ensuring non-adjacency; and (ii) a minimal dominating set, wherein each external node has at least one node as a neighbor in the dominating set. The efficacy and convergence of the algorithms are established through rigorous proofs within the framework of the expression model. Extensive simulation tests validate the algorithms' proficiency in selecting a minimal subset of nodes across expansive network topologies. These algorithms find practical applications in network operations, particularly in ad hoc and wireless sensor networks for the selection of cluster heads that facilitate critical services. Moreover, the self-stabilizing property of the algorithms guarantees the robust reconfiguration of cluster heads post-failure, thereby preserving network functionality amidst disruptions. [ABSTRACT FROM AUTHOR]

In this article the concept of domination in signed graphs is examined from an alternate perspective and a new definition of the same is introduced. A vertex subset D of a signed graph S is a dominating set, if for each vertex v not in D there exists a vertex u ∈ D such that the sign of the edge uv is positive. The domination number γ (S) of S is the minimum cardinality among all the dominating sets of S. We obtain certain bounds of γ (S) and present a necessary and su cient condition for a dominating set to be a minimal dominating set. Further, we characterise the signed graphs having small and large values for domination number.

Claude Berge (1987) introduced the concept of k-extendable graphs, wherein any independent set of size k is inherently a constituent of a maximum independent set within a graph H=(V,E). Graphs possessing the property of being 1-extendable are termedas Berge graphs. This introduction gave rise to the notion of well-covered graphs and well-dominated graphs. A graph is categorized as well-covered if each of its maximal independent sets is, in fact, a maximum independent set. Similarly, a graph attains the classification of well-dominated if every minimal dominating set (DS) within it is a minimum dominating set. In alignment with the concept of k-extendable graphs, the framework of (k,γ)-endowed graphs and symmetric (k,γ)-endowed graphs are established. In these graphs, each DS of size k encompasses a minimum DS of the graph. In this article, a study of γ-endowed dominating sets is initiated. Various results providing a deep insight into γ-endowed dominating sets in graphs such as those characterizing the ones possessing a unique minimum DS are proven. We also introduce and study the symmetric γ-endowed graphs and minimality of dominating sets in them. In addition, we give a solution to an open problem in the literature. which seeks to find a domination-based parameter that has a correlation coefficient of ρ>0.9967 with the total π-electronic energy of lower benzenoid hydrocarbons. We show that the upper dominating number Γ(H) studied in this paper delivers a strong prediction potential.

We consider Upper Domination, the problem of finding the minimal dominating set of maximum cardinality. Very few exact algorithms have been described for solving Upper Domination. In particular, no binary programming formulations for Upper Domination have been described in literature, although such formulations have proved quite successful for other kinds of domination problems. We introduce two such binary programming formulations, and show that both can be improved with the addition of extra constraints which reduce the number of feasible solutions. We compare the performance of the formulations on various kinds of graphs, and demonstrate that (a) the additional constraints improve the performance of both formulations, and (b) the first formulation outperforms the second in most cases, although the second performs better for very sparse graphs. Also included is a short proof that the upper domination number of any generalized Petersen graph P(n, k) is equal to n. [ABSTRACT FROM AUTHOR]

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 $\gamma(G)$. In this work the domination numbers are obtained for family of prism graphs such as prism CL_n, antiprism Q_n and crossed prism R_n by identifying one of their minimum dominating set.

A self-stabilizing distributed algorithm is guaranteed eventually to reach and stay at a legitimate configuration regardless of the initial configuration of a distributed system. In this paper, we propose the generalized dominating set problem, which is a generalization of the dominating set and |$k$| -redundant dominating set problems. In the generalized dominating set we propose in this paper, each node |$P_{i}$| is given its set of domination wish sets, and a generalized dominating set is a set of nodes such that each node is contained in the set or has a wish set in which all its members are in the set. We propose a self-stabilizing distributed algorithm for finding a minimal generalized dominating set in an arbitrary network under the unfair distributed daemon. The proposed algorithm converges in |$O(n^{3}m)$| steps and |$O(n)$| rounds, where |$n$| (resp. |$m$|⁠) is the number of nodes (resp. edges). Furthermore, it has the safe convergence property with safe convergence time in |$O(1)$| rounds. The space complexity of the proposed algorithm is |$O(\Delta \log n)$| bits per node, where |$\Delta $| is the maximum degree of nodes. [ABSTRACT FROM AUTHOR]

The goal of this article provides the common formula for Minimal Domination Cardinality for all Hamiltonian Path or Hamiltonian Circuit. It is explained the way of structures and characteristics of General Hamiltonian Path or Hamiltonian Circuit. It invents the result that all the Hamiltonian Circuit from the given graph should be Cycle Graph. These derived formulae are common for all graphs those have Hamiltonian path or Hamiltonian Circuit. This formula is used to find Maximal Dominating Cardinality in a simple manner. Even though complicated graph also which has Hamiltonian Circuit is evaluating the Cardinality of Maximal Dominating Set is very easy way. [ABSTRACT FROM AUTHOR]

Some of the published results on super strongly perfect graphs are found to be erroneous. We provide some examples and counter examples on the concepts associated with super strongly perfects. [ABSTRACT FROM AUTHOR]

The deployment problem of sensor nodes of Internet of things (IoT) can be abstracted as listing minimal dominating sets of a graph. The problem of listing all the minimal dominating sets in a graph can be converted to the problem of state space search among candidate vertex sets. The search and optimization technologies, such as the bidirectional search and branch cut, can be applied to solve the problem effectively. Our experiments show that the new algorithm can reduce the running time by at least an order of magnitude, compared to a state-of-the-art algorithm for listing all the minimal dominating sets. [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]

Let G be a graph. A set S of vertices in G dominates the graph if every vertex of G is either in S or a neighbor of a vertex in S . Finding a minimum cardinality set which dominates the graph is an NP -complete problem. The graph G is well-dominated if all its minimal dominating sets are of the same cardinality. The complexity status of recognizing well-dominated graphs is not known. We show that recognizing well-dominated graphs can be done polynomially for graphs without cycles of lengths 4 and 5 , by proving that a graph belonging to this family is well-dominated if and only if it is well-covered. Assume that a weight function w is defined on the vertices of G . Then G is w -well-dominated if all its minimal dominating sets are of the same weight. We prove that the set of weight functions w such that G is w -well-dominated is a vector space, and denote that vector space by W W D ( G ) . We show that W W D ( G ) is a subspace of W C W ( G ) , the vector space of weight functions w such that G is w -well-covered. We provide a polynomial characterization of W W D ( G ) for the case that G does not contain cycles of lengths 4 , 5 , and 6 . [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]

This paper proposes a simple and efficient distributed algorithm for calculating minimal dominating set in wireless sensor network. This method can avoid maintaining the connectivities between backbone hosts. Considering that the hosts in mobile networks have different characteristics, this paper proposes a method of calculating minimal dominating set with weight. The nodes can be chosen to form a minimal dominating set when the network topology changes. For the host switch on/off operation, the updating algorithm was provided. The change in the status of a host affects only the status of hosts in the restricted vicinity. Simulation results show that the proposed method can ensure fewer dominators but with higher weight to form the minimal dominating set and the nodes can be adaptive to the changes of network topology. [ABSTRACT FROM AUTHOR]