ProbXiv
Explorersign in
Problem archiveProblem record

Statement

For a finite simple graph GG and a set S⊆V(G)S \subseteq V(G), let c(G−S)c(G - S) denote the number of connected components of the graph obtained from GG by deleting SS. For a real number t≥0t \ge 0, call GG tt-tough if for every integer k>1k > 1 and every S⊆V(G)S \subseteq V(G) with c(G−S)≥kc(G - S) \ge k one has ∣S∣≥tk|S| \ge tk; equivalently, GG is tt-tough if

∣S∣≥t⋅c(G−S)for every S⊆V(G) with c(G−S)>1.|S| \ge t \cdot c(G - S) \quad \text{for every } S \subseteq V(G) \text{ with } c(G - S) > 1 .

(Under this convention every complete graph is tt-tough for every tt, since deleting vertices never leaves more than one component.) A graph GG on n≥3n \ge 3 vertices is Hamiltonian if it contains a cycle passing through each of its nn vertices exactly once.

There exists a real number tt such that every tt-tough graph on at least 33 vertices is Hamiltonian.

Record

Added
Links

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.