Some Theoretical and Practical Results for Edge Dominating Set | ||
| Engineering and Technology Journal | ||
| Article 7, Volume 32, 5B, May 2014, Pages 910-920 PDF (332.01 K) | ||
| DOI: 10.30684/etj.32.5B.8 | ||
| Author | ||
| Nuha A. Rajab | ||
| Abstract | ||
| 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. | ||
| Keywords | ||
| Dominating vertices; minimum edges dominating set; regular graph; independent edges; and incidence matrices | ||
|
Statistics Article View: 155 PDF Download: 51 |
||