Global cycle properties in graphs with large minimum clustering coefficient

DOI10.2989/16073606.2016.1253626MaRDI QIDQ5236152zbMATH OpenOpenAlexFDO

Authors Adam Borchert, Skylar Nicol, Ortrud R. Oellermann

Publication date 15 October 2019

Published in Quaestiones Mathematicae (Search for Journal in Brave)

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)

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.

Recommendations

• Global cycle properties in locally connected, locally traceable and locally Hamiltonian graphs
• Local connectivity, local degree conditions, some forbidden induced subgraphs, and cycle extendability
• A note on cycles in locally Hamiltonian and locally Hamilton-connected graphs
• Global cycle properties of locally isometric graphs
• scientific article; zbMATH DE number 147629

Cites work

• scientific article; zbMATH DE number 3811611 (Why is no real title available?)
• scientific article; zbMATH DE number 3694608 (Why is no real title available?)
• scientific article; zbMATH DE number 3779369 (Why is no real title available?)
• scientific article; zbMATH DE number 3510342 (Why is no real title available?)
• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• scientific article; zbMATH DE number 844152 (Why is no real title available?)
• A note on locally connected and Hamiltonian-connected graphs
• A strengthening of Kikustapos;s theorem
• Collective dynamics of `small-world' networks
• Complexity of the hamiltonian cycle in regular graph problem
• Cycle Extendability and Hamiltonian Cycles in Chordal Graph Classes
• Cycle Extendability of Hamiltonian Interval Graphs
• Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
• Extending cycles in graphs
• Global cycle properties in locally connected, locally traceable and locally Hamiltonian graphs
• Global cycle properties of locally isometric graphs
• Graph theory
• Graphs \& digraphs
• Hamiltonian chordal graphs are not cycle extendable
• Hamiltonian properties of locally connected graphs with bounded vertex degree
• Locally connected graphs
• Pancyclic graphs. I
• Pancyclicity and NP-completeness in planar graphs
• Research problems.
• Some Theorems on Abstract Graphs
• Some localization theorems on Hamiltonian circuits
• Traceability of locally Hamiltonian and locally traceable graphs

Cited in

(3)

• Global cycle properties of locally isometric graphs
• Global cycle properties in locally connected, locally traceable and locally Hamiltonian graphs
• New classes of clustering coefficient locally maximizing 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)