Print ISSN: 1681-6900

Online ISSN: 2412-0758

Author : A. Rajab, Nuha


Some Theoretical and Practical Results for Edge Dominating Set

Nuha A. Rajab

Engineering and Technology Journal, 2014, Volume 32, Issue 5, Pages 910-920

One of the most brilliant branches of modern mathematics and computer applications is graph theory. Graph domination problem has become an extremely important research branch of graph theory in recent times. For instance, determining whether a graph has an induced matching that dominates its edges is a known problem of edges dominating set. Such problems are considered as NP-hard problems. There is, therefore, a growing interest towards finding new algorithms to produce better and more efficient results. In this paper, a new polynomial time algorithm is proposed to determine the set of edge domination. The generalized relations between graph properties (vertices, edges, regularity, and dominating edges) are deduced and abstracted in some important theoretical results, lemmas, propositions, and theorems. One field of applications for this type of domination is a secret sharing scheme. It is implemented to demonstrate its applicability and efficiency.