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]

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]

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]