An Ore-type condition for cyclability

DOI10.1006/EUJC.2001.0517MaRDI QIDQ5949032zbMATH OpenOpenAlexFDO

Authors Yaojun Chen, Yunqing Zhang, Keming Zhang

Publication date 25 September 2002

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/36e7e33a631c0b0cae78ecc2fafcac38058d2708

zbMATH Keywords

cyclabilityHamiltonian digraphOre-type condition

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Review text

A graph \(G\) is said to be cyclable if for each orientation \(D\) of \(G\), there is a set \(S(D)\subseteq V(G)\) such that reversing all arcs with one end in \(S(D)\) results in a Hamiltonian digraph. The authors show that if \(G\) is a simple graph of even order \(n\geq 8\), such that for each pair of non-adjacent vertices \(u,v\in V(G)\), \(d_G(u)+ d_G(v)\geq n+1\), then \(G\) is cyclable. The result is shown to be best possible as \(K_{2t+ 1,2t+1}\) is not cyclable for all \(t\geq 1\).

Recommendations

• A fan-type condition for cyclability
• Neighborhood unions and cyclability of graphs
• Cyclable cube of a graph
• Hamiltonicity and reversing arcs in digraphs
• On the cyclabilitiy of some cube graphs

Cites work

• Hamiltonicity and reversing arcs in digraphs
• scientific article; zbMATH DE number 17787 (Why is no real title available?)
• scientific article; zbMATH DE number 3310759 (Why is no real title available?)
• Note on Hamilton Circuits
• On deciding switching equivalence of graphs
• On graphs that can be oriented as diagrams of ordered sets
• On reorienting graphs by pushing down maximal vertices
• On Ringeisen's isolation game
• Pushing vertices and orienting edges
• Reconstruction from vertex-switching
• Some Theorems on Abstract Graphs
• Switchings Constrained to 2-Connectivity in Simple Graphs
• The isolation game for regular graphs
• Two-Graphs, Switching Classes and Euler Graphs are Equal in Number
• Une condition suffisante d'existence d'un circuit Hamiltonien dans un graphe oriente

Cited in

(11)

• On Ore-type sufficient condition for a bipancyclic ordering
• An Ore-type condition for pancyclability
• Neighborhood unions and cyclability of graphs
• A note on a generalisation of Ore's condition
• A fan-type condition for cyclability
• Cyclable cube of a graph
• On the cyclabilitiy of some cube graphs
• scientific article; zbMATH DE number 5371443 (Why is no real title available?)
• scientific article; zbMATH DE number 4053649 (Why is no real title available?)
• Hamiltonicity and reversing arcs in digraphs
• A sufficient condition for cyclability in directed graphs

This page was built for publication: An Ore-type condition for cyclability

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