Cayley Graphs Defined by Systems of Equations

Abstract

Let R be a finite ring. In this paper, we mainly explore the conditions to ensure the graph BΓn defined by a system of equations {fi|i=2,…,n} to be a Cayley graph or a Hamiltonian graph. More precisely, we prove that BΓn is a Cayley graph with G=⟨ϕ,A⟩ a group of dihedral type if and only if the system Fn={fi|i=2,…,n} is Cayley graphic of dihedral type in R. As an application, the well-known Lova´sz Conjecture, which states that any finite connected Cayley graph has a Hamilton cycle, holds for the connected BΓn defined by Cayley graphic system Fn of dihedral type in the field GF(pk).

Keywords

• Cayley graph
• hamiltonian graph
• dihedral type
• Hamilton-laceable