An extremal problem for cycles in hamiltonian graphs

DOI10.1007/BF01793012MaRDI QIDQ1900521zbMATH OpenOpenAlexFDO

Authors George R. T. Hendry, Stephan Brandt

Publication date 29 November 1995

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01793012

zbMATH Keywords

cycleextremal graphhamiltonian graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Review text

For integers \(p\) and \(r\) with \(3 \leq r \leq p - 1\), let \(f(p,r)\) be the maximum number of edges in a hamiltonian graph of order \(p\) with no cycle of length \(r\). As a consequence of known facts it is remarked that \(f(p,3) = (p - 1)^2/4 + 1\). The main result states that \(f(p,5) = (p - 3)^2/4 + 5\) for all \(p \geq 7\), except \(p = 9\). In this last case there is a unique extremal graph, and \(f(9,5) = 15\). Lower bounds for \(f(p,r)\) are also established in several cases, with \(p\) and \(r\) odd. Some conjectures are proposed for the exact values, together with an explicit description of the candidates to be the corresponding extremal graphs.

Recommendations

• scientific article; zbMATH DE number 4130411
• Publication:3469119
• On the maximum number of cycles in a Hamiltonian graph
• Cycle spectra of Hamiltonian graphs
• scientific article; zbMATH DE number 861428

Cites work

• Cycles of even length in graphs
• Graphs without four-cycles
• Graphs without quadrilaterals
• scientific article; zbMATH DE number 3762094 (Why is no real title available?)
• Large cycles in graphs
• ODD Cycles of Specified Length in Non-Bipartite Graphs
• On critically hamiltonian graphs
• Pancyclic graphs. I
• Sufficient Conditions for Circuits in Graphs^†
• Weakly pancyclic graphs

Cited in

(16)

• A lower bound for the optimal crossing-free Hamiltonian cycle problem
• Weakly pancyclic graphs
• Hamiltonian cycle problem in strong \(k\)-quasi-transitive digraphs with large diameter
• Extremal k-edge-Hamiltonian hypergraphs
• Extremal problems for cycles in graphs
• scientific article; zbMATH DE number 4130411 (Why is no real title available?)
• scientific article; zbMATH DE number 3943849 (Why is no real title available?)
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• scientific article; zbMATH DE number 6829379 (Why is no real title available?)
• scientific article; zbMATH DE number 2170455 (Why is no real title available?)
• scientific article; zbMATH DE number 861428 (Why is no real title available?)
• Cycle Extendability of Hamiltonian Strongly Chordal Graphs
• scientific article; zbMATH DE number 7340788 (Why is no real title available?)
• Feasible Bases for a Polytope Related to the Hamilton Cycle Problem
• Edge-maximal θ2k+1-free non-bipartite Hamiltonian graphs of odd order
• Solution of two problems of P. Erdős concerning Hamiltonian cycles

This page was built for publication: An extremal problem for cycles in hamiltonian graphs

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