China
Africa
Explore chapters and articles related to this topic
Some New Results on Restrained Edge Domination Number of Graphs
Published in N. P. Shrimali, Nita H. Shah, Recent Advancements in Graph Theory, 2020
An edge analogue of a dominating set is also available. A subset F⊆ E is an edge dominating set if each edge in E is either in F or is adjacent to an edge in F. An edge dominating set F is called a minimal edge dominating set if no proper subset F′ of F is an edge dominating set. The minimum cardinality among all minimal edge dominating sets is called the edge domination number, denoted by γre (G). Mitchell and Hedetniemi [9] introduced the concept of edge domination. Yannakakis and Gavril [19] have explored edge dominating sets in graphs while the complementary edge domination in graphs is well studied by Kulli and Soner [8]. Arumugam and Velammal [1] have discussed the edge domination in graphs and edge domination in some path and cycle related graphs is investigated by Vaidya and Pandit [18].
Dominating Set Theory and Algorithms
Published in Jiguo Yu, Xiuzhen Cheng, Honglu Jiang, Dongxiao Yu, Hierarchical Topology Control for Wireless Networks, 2018
Jiguo Yu, Xiuzhen Cheng, Honglu Jiang, Dongxiao Yu
Xiao et al. propose an algorithm with time complexity O(1.3160n), which can calculate an edge dominating set in a graph with n vertices. In the paper, Xiao et al. analyze the algorithm by the Measure and Conquer method and design a branching rule based on simple local structure, which is called “clique-producing vertices/cycles.” The rule makes it easy to analyze the algorithm and its runtime.
Integer linear programming formulations for double roman domination problem
Published in Optimization Methods and Software, 2022
Qingqiong Cai, Neng Fan, Yongtang Shi, Shunyu Yao
A set is called a dominating set if every vertex of G is either in S or adjacent to a vertex of S. The minimum cardinality of a dominating set in G, denoted by , is called the domination number. Domination of graphs has been extensively studied in the scientific literature. The variants of domination have abundant applications, including error-correcting codes constructions for digital communication and efficient data routing in wireless networks [9,10,12,18,28]. Many different kinds of domination arose, such as the connected dominating set [16], the edge dominating set [33], the total domination [24,27], the independent domination [19], Roman domination [32], etc.