Discussiones Mathematicae Graph Theory, Vol. 30, pp. 591-609, 2010.
David AUGER, Irène CHARON, Olivier HUDRY & Antoine LOBSTEIN
Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
{auger, charon, hudry, lobstein}@enst.fr
Abstract. We consider a simple, undirected graph G. The ball of a subset Y of vertices in G is the set of vertices in G at distance at most 1 from a vertex in Y. Assuming that the balls of all subsets of at most two vertices in G are distinct, we prove that G admits a cycle with length at least 7.