Hamiltonicity of 3-arc graphs

DOI10.1007/S00373-013-1329-5zbMATH Open1298.05194arXiv1201.5707OpenAlexW1990977401MaRDI QIDQ742645FDOQ742645

Authors: Guangjun Xu, Sanming Zhou 

Publication date: 19 September 2014

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

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.

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

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)