Global cycle properties in graphs with large minimum clustering coefficient

DOI10.2989/16073606.2016.1253626zbMATH Open1422.05056arXiv1506.03691OpenAlexW2963878341MaRDI QIDQ5236152FDOQ5236152

Skylar Nicol, Ortrud R. Oellermann, Adam Borchert

Publication date: 15 October 2019

Published in: Quaestiones Mathematicae (Search for Journal in Brave)

Abstract: The clustering coefficient of a vertex in a graph is the proportion of neighbours of the vertex that are adjacent. The minimum clustering coefficient of a graph is the smallest clustering coefficient taken over all vertices. A complete structural 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 strongly induced subgraphs with given attachment sets. Moreover, it is shown that all locally connected graphs with minimum clustering coefficient 1/2 and maximum degree at most 6 are weakly pancyclic, thereby proving Ryjacek's conjecture for this class of locally connected graphs.

Full work available at URL: https://arxiv.org/abs/1506.03691

zbMATH Keywords

locally connectedfully-cycle extendableminimum clustering coefficientRyjáček's conjecturestrongly induced sub-graphs

Mathematics Subject Classification ID

Paths and cycles (05C38)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Collective dynamics of ‘small-world’ networks
• A note on locally connected and Hamiltonian-connected graphs
• Complexity of the hamiltonian cycle in regular graph problem
• Research problems.
• Pancyclicity and NP-completeness in planar graphs
• Pancyclic graphs. I
• Global cycle properties of locally isometric graphs
• Global cycle properties in locally connected, locally traceable and locally Hamiltonian graphs
• Traceability of locally Hamiltonian and locally traceable graphs
• A strengthening of Kikustapos;s theorem
• Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
• Locally connected graphs
• Some Theorems on Abstract Graphs
• Hamiltonian properties of locally connected graphs with bounded vertex degree
• Extending cycles in graphs
• Some localization theorems on Hamiltonian circuits
• Cycle Extendability of Hamiltonian Interval Graphs
• Cycle Extendability and Hamiltonian Cycles in Chordal Graph Classes
• Hamiltonian Chordal Graphs are not Cycle Extendable

Cited In (1)

• Global cycle properties of locally isometric graphs

This page was built for publication: Global cycle properties in graphs with large minimum clustering coefficient

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236152)