International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
Volume 50 - Issue 12 |
Published: July 2012 |
Authors: M. I. Moussa, E. M. Badr |
![]() |
M. I. Moussa, E. M. Badr . A Computational Study for the Graph-theoretic Version of the Union-closed Sets Conjecture. International Journal of Computer Applications. 50, 12 (July 2012), 1-5. DOI=10.5120/7820-0945
@article{ 10.5120/7820-0945, author = { M. I. Moussa,E. M. Badr }, title = { A Computational Study for the Graph-theoretic Version of the Union-closed Sets Conjecture }, journal = { International Journal of Computer Applications }, year = { 2012 }, volume = { 50 }, number = { 12 }, pages = { 1-5 }, doi = { 10.5120/7820-0945 }, publisher = { Foundation of Computer Science (FCS), NY, USA } }
%0 Journal Article %D 2012 %A M. I. Moussa %A E. M. Badr %T A Computational Study for the Graph-theoretic Version of the Union-closed Sets Conjecture%T %J International Journal of Computer Applications %V 50 %N 12 %P 1-5 %R 10.5120/7820-0945 %I Foundation of Computer Science (FCS), NY, USA
An induced subgraph S of a graph G is called a derived subgraph of G if S contains no isolated vertices. An edge e of G is said to be residual if e occurs in more than half of the derived subgraphs of G. We prove some theorems which calculate the number of derived subgraphs for some special graphs. We also present a new algorithm SDSA that calculates the number of derived subgraphs for a given graph G and determines the residual and non-residual edges. Finally, we introduce a computational study which supports our results.