Premium
A graph‐theoretic version of the union‐closed sets conjecture
Author(s) -
ElZahar Mohamed H.
Publication year - 1997
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199711)26:3<155::aid-jgt6>3.0.co;2-q
Subject(s) - combinatorics , mathematics , conjecture , collatz conjecture , discrete mathematics , graph , induced subgraph , vertex (graph theory)
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. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 155–163, 1997