Hamiltonicity of 3-arc graphs

Details Hamiltonicity of 3-arc graphs Hamiltonicity of 3-arc graphs

2012-01-27

arxiv.org/abs/1201.5707v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Hamiltonicity of 3-arc graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hamiltonicity of 3-arc graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hamiltonicity of 3-arc graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-344356