Subgraphs intersecting any Hamiltonian cycle

DOI10.1016/0095-8956(88)90097-4MaRDI QIDQ1077429zbMATH OpenOpenAlexFDO

Authors Peter Horák

Publication date 1988

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(88)90097-4

zbMATH Keywords

hamiltonian cyclemaximal non-hamiltonian graphsubgraphvertex covering

Mathematics Subject Classification ID

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

Review text

Let G be a subgraph of K(n), the complete graph on n vertices, such that (i) its edges cannot be represented by fewer than k vertices, (ii) every hamiltonian cycle of K(n) contains at least one edge of G and no proper subgraph of G has this property. P. Erdős posed the question of determining min e(G). In particular, is there an absolute constant c such that e(G)\(\geq c\cdot k\cdot n?\) The minimum is calculated for all \(n\geq 3\) and \(k\leq n/2\), and the second part of the question is answered in the affirmative with \(c=1/4\) being the best possible constant.

Recommendations

• scientific article; zbMATH DE number 861428
• MinimumK-hamiltonian graphs
• Publication:3469119
• The number of cycles in a Hamilton graph
• scientific article; zbMATH DE number 4152419

Cites work

• A catalogue of small maximal nonhamiltonian graphs
• A method in graph theory
• Arc coverings of graphs
• scientific article; zbMATH DE number 3869331 (Why is no real title available?)
• scientific article; zbMATH DE number 3689432 (Why is no real title available?)
• scientific article; zbMATH DE number 3186566 (Why is no real title available?)
• On a construction of Thomassen
• On Hamilton's ideals
• On Representatives of Subsets
• Variations on the Hamiltonian Theme

Cited in

(4)

• The number of edges in a subgraph of a Hamming graph
• Minimum multiplicities of subgraphs and Hamiltonian cycles
• scientific article; zbMATH DE number 861428 (Why is no real title available?)
• Solution of two problems of P. Erdős concerning Hamiltonian cycles

This page was built for publication: Subgraphs intersecting any Hamiltonian cycle

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