Local connectivity, local degree conditions, some forbidden induced subgraphs, and cycle extendability

DOI10.1016/J.DISC.2016.11.035zbMATH Open1355.05144arXiv1507.07486OpenAlexW2221661363MaRDI QIDQ507477FDOQ507477

Authors: Christoph Brause, Dieter Rautenbach, Ingo Schiermeyer 

Publication date: 6 February 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: The research in the present paper was motivated by the conjecture of Ryj'{a}v{c}ek that every locally connected graph is weakly pancyclic. For a connected locally connected graph $G$ of order at least $3$, our results are as follows: If $G$ is $(K_1+(K_{1}cup{K}_2))$-free, then $G$ is weakly pancyclic. If $G$ is $(K_1+(K_{1}cup{K}_2))$-free, then $G$ is fully cycle extendable if and only if $2delta(G)geqn(G)$. If $G$ is $$-free or $$-free, then $G$ is fully cycle extendable. If $G$ is distinct from $$ and $K_1+P_4,K_{1,4},K_2+(K_{1}cup{K}_2)$-free, then $G$ is fully cycle extendable. Furthermore, if $G$ is a connected graph of order at least $3$ such that ${\displaystyle }$|N_G(u)cap N_G(v)cap N_G(w)|>|N_G(u)setminus (N_G[v]cup N_G[w])|${\displaystyle }$ for every induced path $vuw$ of order $3$ in $G$, then $G$ is fully cycle extendable, which implies that every connected locally Ore or locally Dirac graph of order at least $3$ is fully cycle extendable.

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

Recommendations

• A note on cycles in locally Hamiltonian and locally Hamilton-connected graphs
• Global cycle properties in locally connected, locally traceable and locally Hamiltonian graphs
• Global cycle properties of locally isometric graphs
• Full cycle extendability of locally connected \(K_{1,4}\)-restricted graphs
• A strengthening of Kikustapos;s theorem

zbMATH Keywords

cyclefully cycle extendableweakly pancyclicforbidden induced subgraphlocal connectivity

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40)

Cites Work

• Note on Hamilton Circuits
• A strengthening of Kikustapos;s theorem
• Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
• Title not available (Why is that?)
• Title not available (Why is that?)
• Locally connected graphs
• Some Theorems on Abstract Graphs
• Hamiltonian properties of locally connected graphs with bounded vertex degree
• Some localization theorems on Hamiltonian circuits
• Title not available (Why is that?)
• Title not available (Why is that?)
• Cycles of given length in some \(K_{1,3}\)-free graphs

Cited In (10)

• Global cycle properties in locally connected, locally traceable and locally Hamiltonian graphs
• Global cycle properties in graphs with large minimum clustering coefficient
• Full cycle extendability of locally connected \(K_{1,4}\)-restricted graphs
• Forbidden subgraphs and weak locally connected graphs
• A local independence number condition for \(n\)-extendable graphs
• Deficiency and forbidden subgraphs of connected, locally-connected graphs
• Toughness, forbidden subgraphs and pancyclicity
• A note on cycles in locally Hamiltonian and locally Hamilton-connected graphs
• A local intersection condition for \(n\)-extendable graphs
• A strengthening of Kikustapos;s theorem

This page was built for publication: Local connectivity, local degree conditions, some forbidden induced subgraphs, and cycle extendability

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