Symmetries and symmetry-breaking in arithmetic graphs

Abstract

In this paper, we study symmetries and symmetry-breaking of the arithmetic graph of a composite number m, denoted by Am. We first study some properties such as the distance between vertices, the degree of a vertex and the number of twin classes in the arithmetic graphs. We describe symmetries of Am and prove that the automorphism group of Am is isomorphic to the symmetric group Sn of n elements, for m=∏i=1npi. For symmetry-breaking, we study the concept of the fixing number of the arithmetic graphs and give exact formulae of the fixing number for the arithmetic graphs Am for m=∏i=1npiri under different conditions on ri.

Keywords

• Arithmetic graph
• Automorphism
• Symmetry-breaking
• Twins
• Fixing number