Premium
Normal cirulant graphs with noncyclic regular subroups
Author(s) -
Marušič Dragan,
Morris Joy
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20088
Subject(s) - mathematics , combinatorics , cayley graph , dihedral group , discrete mathematics , cyclic group , circulant matrix , abelian group , vertex transitive graph , converse , cayley's theorem , chordal graph , prime (order theory) , graph , group (periodic table) , line graph , voltage graph , chemistry , geometry , organic chemistry
Abstract We prove that any circulant graph of order n with connection set S such that n and the order of ℤ n * ( S ), the subgroup of ℤ n *that fixes S set‐wise, are relatively prime, is also a Cayley graph on some noncyclic group, and shows that the converse does not hold in general. In the special case of normal circulants whose order is not divisible by 4, we classify all such graphs that are also Cayley graphs of a noncyclic group, and show that the noncyclic group must be metacyclic, generated by two cyclic groups whose orders are relatively prime. We construct an infinite family of normal circulants whose order is divisible by 4 that are also normal Cayley graphs on dihedral and noncyclic abelian groups. © 2005 Wiley Periodicals, Inc. J Graph Theory