A graph-theoretic version of the union-closed sets conjecture
✍ Scribed by El-Zahar, Mohamed H.
- Publisher
- John Wiley and Sons
- Year
- 1997
- Tongue
- English
- Weight
- 128 KB
- Volume
- 26
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
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 introduce the conjecture: Every non-empty graph contains a non-residual edge. This conjecture is implied by, but weaker than, the union-closed sets conjecture. We prove that a graph G of order n satisfies this conjecture whenever G satisfies any one of the conditions: δ(G) ≤ 2, log 2 n ≤ δ(G), n ≤ 10, or the girth of G is at least 6. Finally, we show that the union-closed sets conjecture, in its full generality, is equivalent to a similar conjecture about hypergraphs.