Triangles and neighbourhoods of independent sets in graphs (Q1850489): Difference between revisions

It is proved that a graph \(G\) of order \(n\) contains a triangle if \(|N(X)|> {1\over 3}(n+|X|)\) for every nonempty independent set \(X\) of vertices. If, in addition, \(G\) is 2-connected, then \(G\) is pancyclic (that is, it contains cycles of all lengths \(l\), \(3\leq l\leq n\)). The bound \({1\over 3}(n+|X|)\) is sharp in both cases, and the condition for \(G\) to be pancyclic is essentially the same as the known sharp condition \((\delta(G)\geq{1\over 3} (n+2)\) and \(|N(X)|\geq{1\over 3} (n+|X|- 1)\)) for a 2-connected graph \(G\) to be Hamiltonian. The paper concludes with the following conjecture of Yair Caro: If \(k\geq 2\) is an integer and \(G\) is a graph of order \(n\) such that \(|N(X)|> (k-2)(n+ |X|)/k\) for every nonempty independent set \(X\) of vertices, then \(G\) contains a copy of \(K_k\), the complete graph on \(k\) vertices. This is obvious when \(k=2\), and is the main result of this paper when \(k=3\). The Turán graphs show that, if true, it is sharp for all \(k\).