Triangles and neighbourhoods of independent sets in graphs
type: Item
instance of: scholarly article
title: Triangles and neighbourhoods of independent sets in graphs
zbMATH Open document ID: 1023.05087
author: Andrew M. Robertshaw
author: Douglas R. Woodall
published in: Journal of Combinatorial Theory. Series B
publication date: 2002-12-10T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1843720
zbMATH Keywords: binding number
zbMATH Keywords: neighbourhood condition
zbMATH Keywords: triangle-free graph
zbMATH Keywords: pancyclic
zbMATH Keywords: conjecture of Caro
zbMATH Keywords: Turán graphs
MaRDI profile type: Publication
full work available at URL: jctb.2000.1974
OpenAlex ID: W2015893985
cites work: Perfect matchings of a graph
cites work: Q4889849
cites work: A note on maximal triangle‐free graphs
cites work: The binding number of a graph and its triangle
cites work: The binding number of a graph and its pancyclism
cites work: The binding number of a graph and its Anderson number
cites work: A sufficient condition for Hamiltonian circuits
cites work: k -Factors and Neighbourhoods of Independent Sets in Graphs
DOI: 10.1006/JCTB.2000.1974
description: scientific article; zbMATH DE number 1843720