ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Call a finite simple graph Γ\Gamma vertex-transitive if its automorphism group acts transitively on V(Γ)V(\Gamma), and call a cycle in Γ\Gamma Hamiltonian if it passes through every vertex of Γ\Gamma exactly once.

For a cubic graph XX (every vertex of degree 33), let T(X)T(X) denote the triangle replacement of XX: the vertex set of T(X)T(X) is the set of pairs (v,e)(v,e) with v∈V(X)v\in V(X), e∈E(X)e\in E(X) and vv an endpoint of ee; two such pairs (v,e)(v,e) and (w,f)(w,f) are adjacent in T(X)T(X) if either v=wv=w and e≠fe\neq f (so the three pairs at each vertex of XX form a triangle), or e=fe=f and v≠wv\neq w.

Let PP be the Petersen graph, i.e. the graph whose vertices are the 22-element subsets of {1,2,3,4,5}\{1,2,3,4,5\}, two such subsets being adjacent when they are disjoint.

Let CC be the Coxeter graph, i.e. the graph on the 2828 vertices

{ai,  bi,  ci,  vi  :  i∈Z7}\{a_i,\;b_i,\;c_i,\;v_i \;:\; i\in\mathbb{Z}_7\}

with edges aiai+1a_i a_{i+1}, bibi+2b_i b_{i+2}, cici+3c_i c_{i+3}, and viaiv_i a_i, vibiv_i b_i, viciv_i c_i for all i∈Z7i\in\mathbb{Z}_7.

Then every finite connected vertex-transitive graph contains a Hamiltonian cycle, with the exception of exactly five graphs up to isomorphism, namely

K2,P,C,T(P),T(C),K_2,\quad P,\quad C,\quad T(P),\quad T(C),

each of which is finite, connected and vertex-transitive, contains a Hamiltonian path, and contains no Hamiltonian cycle.

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.