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

DOI10.1016/J.DISC.2016.11.035MaRDI QIDQ507477zbMATH OpenOpenAlexFDO

Authors Christoph Brause, Dieter Rautenbach, Ingo Schiermeyer

Publication date 6 February 2017

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

cyclefully cycle extendableweakly pancyclicforbidden induced subgraphlocal connectivity

Mathematics Subject Classification ID

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

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.

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

Cites work

• 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 844152 (Why is no real title available?)
• scientific article; zbMATH DE number 1409241 (Why is no real title available?)
• A strengthening of Kikustapos;s theorem
• Cycles of given length in some \(K_{1,3}\)-free graphs
• Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
• Hamiltonian properties of locally connected graphs with bounded vertex degree
• Locally connected graphs
• Note on Hamilton Circuits
• Some Theorems on Abstract Graphs
• Some localization theorems on Hamiltonian circuits

Cited in

(10)

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

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)