On conjectures of Frankl and El‐Zahar |
| |
| Authors: | Bernardo Llano Juan José Montellano‐Ballesteros Eduardo Rivera‐Campo Ricardo Strausz |
| |
| Institution: | 1. Departamento de Matemáticas, Universidad Autónoma Metropolitana‐Izt Morelia, Michoacán, Mexico;2. Instituto de Matmáticas, Universidad Nacional Autónoma de México Morelia, Michoacán, Mexico |
| |
| Abstract: | An induced subgraph  of a graph  is called a derived subgraph of  if  contains no isolated vertices. An edge e of  is said to be residual if e occurs in more than half of the derived subgraphs of  . In this article, we prove that every simple graph with at least one edge contains a non‐residual edge. This was conjectured by El‐Zahar in 1997. © 2008 Wiley Periodicals, Inc. J Graph Theory 57: 344–352, 2008 |
| |
| Keywords: | union closed sets conjecture induced graphs |
|
|
