A Computational Study for the Graph-theoretic Version of the Union-closed Sets Conjecture

Print
International Journal of Computer Applications
© 2012 by IJCA Journal
Volume 50 - Number 12
Year of Publication: 2012
Authors:
M. I. Moussa
E. M. Badr
10.5120/7820-0945

M I Moussa and E M Badr. Article: A Computational Study for the Graph-theoretic Version of the Union-closed Sets Conjecture. International Journal of Computer Applications 50(12):1-5, July 2012. Full text available. BibTeX

@article{key:article,
	author = {M. I. Moussa and E. M. Badr},
	title = {Article: 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},
	month = {July},
	note = {Full text 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.

References

  • I. Rival (Ed. ), Graphs And Order, Reidel, Dordrecht-Boston,(1985), p. 25.
  • R. P. Stanley, Enumerative Combinatorics, vol. I, Wadsworth & Broks/Cole, Belmont, CA, (1986).
  • B. Poonen, Union-Closed Families, J. Combin. Theory, A 59 (1992), 253-268.
  • M. H. El-Zahar , A Graph-Theoretic Version Of The Union-Closed Sets Conjecture, J. Graph Theory 26 (1997), no. 3, 155-163.
  • B. Llano, J. Montellano-Ballesteros, E. Rivera-Campo and R. Strauz " On Conjecture of Frankl and El-Zahar" J. Graph Theory 57: 344-352 (2008).
  • G. Chartrand and L. Lesniak " Graphs & Digraphs" (third edition) Chaman & Hall, London, (1996) .