| publication name | M. I. Moussa and E. M. Badr (2012): A Computational Study for the Graph-Theoretic Version of the Union-Closed Sets Conjecture, International Journal of Computer Applications, Volume 50 – No.12, July 2012. |
|---|---|
| Authors | M. I. Moussa and E. M. Badr |
| year | 2012 |
| keywords | |
| journal | |
| volume | Not Available |
| issue | Not Available |
| pages | Not Available |
| publisher | Not Available |
| Local/International | International |
| Paper Link | http://www.ijcaonline.org/archives/volume50/number12/7820-0945 |
| Full paper | download |
| Supplementary materials | Not Available |
Abstract
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.