CFP last date
22 April 2024
Reseach Article

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

by M. I. Moussa, E. M. Badr
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 50 - Number 12
Year of Publication: 2012
Authors: M. I. Moussa, E. M. Badr
10.5120/7820-0945

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 },
issue_date = { July 2012 },
volume = { 50 },
number = { 12 },
month = { July },
year = { 2012 },
issn = { 0975-8887 },
pages = { 1-5 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume50/number12/7820-0945/ },
doi = { 10.5120/7820-0945 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:48:04.674441+05:30
%A M. I. Moussa
%A E. M. Badr
%T A Computational Study for the Graph-theoretic Version of the Union-closed Sets Conjecture
%J International Journal of Computer Applications
%@ 0975-8887
%V 50
%N 12
%P 1-5
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
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
  1. I. Rival (Ed. ), Graphs And Order, Reidel, Dordrecht-Boston,(1985), p. 25.
  2. R. P. Stanley, Enumerative Combinatorics, vol. I, Wadsworth & Broks/Cole, Belmont, CA, (1986).
  3. B. Poonen, Union-Closed Families, J. Combin. Theory, A 59 (1992), 253-268.
  4. M. H. El-Zahar , A Graph-Theoretic Version Of The Union-Closed Sets Conjecture, J. Graph Theory 26 (1997), no. 3, 155-163.
  5. 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).
  6. G. Chartrand and L. Lesniak " Graphs & Digraphs" (third edition) Chaman & Hall, London, (1996) .
Index Terms

Computer Science
Information Sciences

Keywords

Union closed sets conjecture induced graphs derived subgraphs