A bijection between aperiodic palindromes and connected circulant graphs

2014/12/08 by Hunki Baek, Baek, Hunki, Sejeong Bang +5
Mathematics · #05C30 05A17 05C25 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.1412.2426

openalex publication_date 2014/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we show that there is a one-to-one correspondence between the set of compositions (resp. prime compositions) of n and the set of circulant digraphs (resp. connected circulant digraphs) of order n. We also show that there is a one-to-one correspondence between the set of palindromes (resp. aperiodic palindromes) of n and the set of circulant graphs (resp. connected circulant graphs) of order n. As a corollary of this correspondence, we enumerate the number of connected circulant (di)graphs of order n.

Related

• On the Enumeration of Circulant Graphs of Prime-Power Order: the case of p³
• A classification of locally-quasiprimitive circulant digraphs
• Automorphism groups of circulant graphs -- a survey
• Constructive and analytic enumeration of circulant graphs with p³ vertices; p=3,5
• Circulants and their connectivities