Characterization And Structure Of A Power Set Graph
Volume 3 - Issue 6, June 2019 Edition
[Download Full Paper]
Author(s)
Melody Mae Cabigting Lunar, Renson Aguilar Robles
Keywords
Power Set Graph, Dominance Number, Independence Number.
Abstract
This study introduced a simple graph called the Power Set Graph. This graph is taken from the lattice diagram of a power set. Let A be a finite nonempty set with cardinality n. The Power Set Graph, denoted by , is the graph where is the power set of A and adjacency is defined by for all if and only if or . The study determined the characterization and structure of this graph including its size, order, independence number and dominance number. Results of the study showed that the power set graph is a simple graph with degree , dominance number, and independence number, if n is odd and if n is even. Also, this paper showed the explicit formula to determine the size of the power set graph.
References
[1]. O. Kuchaiev and N. Przulj, “Learning the Structure of Protein – Protein In-teraction Networks. Pacific Symposium on Biocomputing, 39-50. 10.1142/9789812836939_0005. 2009
[2]. A. Balaban, “Chemical Graph Theory and Sherlock Holmes Principleâ€. International Journal for Philosophy of Chemistry, 19,107-134. 2013
[3]. A. Sobota A. and R. Zochowska, “Model of Urban Public Transportation Network for the Analysis of Punctualityâ€, Journal of Achievements in Materials and Manufacturing Engineering. Vol. 28. Issue 1. 2008
[4]. K. Atkins, J. Chen, V.S. Kumar and A. Marathe, “The Structure of Electrical Networks: A Graph Theory-Based Analysis†International Journal on Critical Infrastractures, Vol. 5, No. 3. 2009
[5]. H. Robinson, “Graph Theory Techniques in Model-Based Testingâ€. International Conference on Testing Computer Software. 1999
[6]. F. Harary. “Graph Theory†Addison – Wesley Publishing Company Inc. 1994
[7]. G. Chartrand and P. Zhang, “Introduction to Graph Theoryâ€, Mc Graw Hill, Reading, Singapore. 2005
[8]. L. Leithold, “College Algebra and Trigonometry†Pearson Education Asia Pte Ltd., Singapore. 2002
