Hamiltonicity of 3-arc graphs

DOI10.1007/S00373-013-1329-5MaRDI QIDQ742645zbMATH OpenOpenAlexFDO

Authors Guangjun Xu, Sanming Zhou

Publication date 19 September 2014

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

Full work available at URL https://arxiv.org/abs/1201.5707

zbMATH Keywords

Hamilton cycleHamiltonian graphvertex-transitive graphHamilton-connected graph3-arc graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Connectivity (05C40)

Abstract: An arc of a graph is an oriented edge and a 3-arc is a 4-tuple $(v,u,x,y)$ of vertices such that both $(v,u,x)$ and $(u,x,y)$ are paths of length two. The 3-arc graph of a graph $G$ is defined to have vertices the arcs of $G$ such that two arcs $uv,xy$ are adjacent if and only if $(v,u,x,y)$ is a 3-arc of $G$. In this paper we prove that any connected 3-arc graph is Hamiltonian, and all iterative 3-arc graphs of any connected graph of minimum degree at least three are Hamiltonian. As a consequence we obtain that if a vertex-transitive graph is isomorphic to the 3-arc graph of a connected arc-transitive graph of degree at least three, then it is Hamiltonian. This confirms the well known conjecture, that all vertex-transitive graphs with finitely many exceptions are Hamiltonian, for a large family of vertex-transitive graphs. We also prove that if a graph with at least four vertices is Hamilton-connected, then so are its iterative 3-arc graphs.

Recommendations

• Diameter and connectivity of 3-arc graphs
• A study of 3-arc graphs
• k-Arc Hamilton graphs
• Three-arc graphs: characterization and domination
• On the connectivity and restricted edge-connectivity of 3-arc graphs

Cites work

• scientific article; zbMATH DE number 3733976 (Why is no real title available?)
• scientific article; zbMATH DE number 2149409 (Why is no real title available?)
• scientific article; zbMATH DE number 863469 (Why is no real title available?)
• A class of finite symmetric graphs with 2-arc transitive quotients
• A study of 3-arc graphs
• Advances on the Hamiltonian problem -- a survey
• Almost covers of 2-arc transitive graphs
• CROSS RATIO GRAPHS
• Constructing a class of symmetric graphs
• Diameter and connectivity of 3-arc graphs
• Eulerian subgraphs and Hamilton-connected line graphs
• Finite symmetric graphs with two-arc transitive quotients
• Finite symmetric graphs with two‐arc transitive quotients II
• Graph theory
• Graph theory
• Hamilton connectivity of line graphs and claw‐free graphs
• Hamilton cycles and paths in vertex-transitive graphs-current directions
• Hamilton-connected Cayley graphs on Hamiltonian groups
• Hamilton-connected indices of graphs
• Hamiltonicity of 6-connected line graphs
• Imprimitive symmetric graphs, 3-arc graphs and 1-designs
• On Hamiltonian Line-Graphs
• On the connectivity and restricted edge-connectivity of 3-arc graphs
• Reflections on graph theory
• Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface

Cited in

(5)

• Hadwiger's conjecture for 3-arc graphs
• A study of 3-arc graphs
• Diameter and connectivity of 3-arc graphs
• Arc diagrams, flip distances, and Hamiltonian triangulations
• Three-arc graphs: characterization and domination

This page was built for publication: Hamiltonicity of 3-arc graphs

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