You are in:Home/Publications/ 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. | |
Prof. Alsayed alsayed mitwali badr :: Publications: |
Title: | 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: | Not Available |
Journal: | Not Available |
Volume: | Not Available |
Issue: | Not Available |
Pages: | Not Available |
Publisher: | Not Available |
Local/International: | International |
Paper Link: | |
Full paper | Alsayed alsayed mitwali badr_pxc3880945.pdf |
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. |