2020/05/13 by M. H. Bani Mostafa A., A., M. H. Bani Mostafa, Ebrahim Ghorbani +1
Computer Science · #05C78 #11B75 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2005.06308
openalex publication_date 2020/05/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The k-coprime graph of order n is the graph with vertex set \k, k+1, …, k+n-1\ in which two vertices are adjacent if and only if they are coprime. We characterize Hamiltonian k-coprime graphs. As a particular case, two conjectures by Tout, Dabboucy, Howalla (1982) and by Schroeder (2019) on prime labeling of 2-regular graphs follow. A prime labeling of a graph with n vertices is a labeling of its vertices with distinct integers from \1, 2,… , n\ in such a way that the labels of any two adjacent vertices are relatively prime.