Global cycle properties in graphs with large minimum clustering coefficient

Abstract

Let ???? be a graph property. A graph G is said to be locally ???? (closed locally ????) if the subgraph induced by the open neighbourhood (closed neighbourhood, respectively) of every vertex in G has property ????. 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 |V (C)| + 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 specified attachment sets). Moreover, it is shown that all locally connected graphs with Δ ≤ 6 and sufficiently large minimum clustering coefficient are weakly pancylic, thereby proving Ryj´ǎcek’s conjecture for this class of graphs.