Journal of Mathematics and Statistics

Disjoint Sets in Graphs and its Application to Electrical Networks

Ford Lumban Gaol

DOI : 10.3844/jmssp.2011.73.77

Journal of Mathematics and Statistics

Volume 7, Issue 1

Pages 73-77

Abstract

Problem statement: One of the well known problems in Telecommunication and Electrical Power System is how to put Electrical Sensor Unit (ESU) in some various selected locations in the system. Approach: This problem was modeled as the vertex covering problems in graphs. The graph modeling of this problem as the minimum vertex covering set problem. Results: The degree covering set of a graph for every vertex is covered by the set minimum cardinality. The minimu of a graph cardinality of a degree covering set of a graph G is the degree covering number γP(G). Conclusion: We show that Degree Covering Set (DCS) problem is NP-complete. In this study, we also give a linear algorithm to solve the DCS for trees. In addition, we investigate theoretical properties of γP (T) in trees T.

Copyright

© 2011 Ford Lumban Gaol. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.