Global cycle properties in graphs with large minimum clustering coefficient

Abstract

Let P be a graph property. A graph G is said to be locally P (closed locally P) if the subgraph induced by the open neighbourhood (closed neighbourhood, respectively) of every vertex in G has property P. The clustering coefficient of a vertex is the proportion of pairs of its neighbours that are themselves neighbours. The minimum clustering coefficient of G is the smallest clustering coefficient among all vertices of G. Let H be a subgraph of a graph G and let S V (H). We say that H is a strongly induced subgraph of G with attachment set S, if H is an induced subgraph of G and the vertices of V (H) -S are not incident with edges that are not in H. A graph G is fully cycle extendable if every vertex of G lies in a triangle and for every  nonhamiltonian cycle C of G, there is a cycle of length jV (C)j+1 that contains the vertices of C. A complete characterization, of those locally connected graphs with minimum clustering coefficient 1/2 and maximum degree at most 6 that are fully cycle extendable, is given in terms of forbidden strongly induced subgraphs (with specied attachment sets). Moreover, it is shown that all locally connected graphs with Δ < 6 and sufficiently large minimum clustering coefficient are weakly pancylic, thereby proving Ryjacek's conjecture for this class of graphs.

Mathematics Subject Classication (2010): 05C38.

Key words: Minimum clustering coefficient, locally connected, strongly induced sub-
graphs, fully-cycle extendable, Ryjacek's conjecture.