Existence of graphs with specified cycle lengths

DOI10.1016/0012-365X(89)90169-6MaRDI QIDQ913817zbMATH OpenOpenAlexFDO

Authors William McCuaig

Publication date 1989

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(89)90169-6

zbMATH Keywords

cyclelength

Mathematics Subject Classification ID

Paths and cycles (05C38)

Review text

The two following theorems are proved. Let n,g\(\geq 3\) and let \(I\subseteq \{3,...,g\}.\) There exists an n-regular n-connected graph G such that for every \(i\in \{3,...,g\},\) G has a cycle of length i if and only if \(i\in I\). Let \(m,d\geq 1\) and let \(J\subseteq \{0,1,...,d\}.\) There exists an m- connected graph H such that for every \(i\in \{0,1,...,d\},\) H has a cycle of length v(H)-i if and only if \(i\in J\).

Recommendations

• Long cycles through specified vertices in a graph
• Longest cycles in regular graphs
• scientific article; zbMATH DE number 4212091
• Cycle lengths in graphs with large minimum degree
• scientific article; zbMATH DE number 4103118

Cites work

• Graph theory
• On r-regular r-connected non-hamiltonian graphs
• Regular Graphs with Given Girth and Restricted Circuits

Cited in

(10)

• Graphs such that every two edges are contained in a shortest cycle
• Cycle-regular graphs
• A Cauchy-Davenport type result for arbitrary regular graphs
• Arena graph
• scientific article; zbMATH DE number 4177104 (Why is no real title available?)
• On the existence of a specified cycle in digraphs with constraints on degrees
• Circumference of a regular graph
• scientific article; zbMATH DE number 151768 (Why is no real title available?)
• scientific article; zbMATH DE number 1205987 (Why is no real title available?)
• Cycle-regular graphs of \((0,\lambda )\)-graph type

This page was built for publication: Existence of graphs with specified cycle lengths

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