Hamiltonicity of a coprime graph

DOI10.1007/S00373-021-02362-1MaRDI QIDQ2053700zbMATH OpenOpenAlexFDO

Authors M. H. Bani Mostafa A., E. Ghorbani

Publication date 30 November 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.06308

zbMATH Keywords

2-regular graphcoprime graphprime labeling

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Other combinatorial number theory (11B75)

Abstract: The $k$-coprime graph of order $n$ is the graph with vertex set $k,k+1,ldots,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,ldots,n$ in such a way that the labels of any two adjacent vertices are relatively prime.

Recommendations

• Hamiltonicity in prime sum graphs
• scientific article; zbMATH DE number 4123770
• scientific article; zbMATH DE number 1161243
• Hamiltonicity of Complements of Total Graphs
• scientific article; zbMATH DE number 57115
• On hyper-Hamiltonicity in graphs
• scientific article; zbMATH DE number 1180503
• Hamiltonicity in connected regular graphs
• Hamilton decompositions of graphs with primitive complements
• Hamiltonicity and $\sigma$-hypergraphs

Cites work

• A dynamic survey of graph labeling
• A Survey of Problems in Combinatorial Number Theory
• Complete tripartite subgraph in the coprime graphs of integers
• Every cubic bipartite graph has a prime labeling except \(K_{3,3}\)
• scientific article; zbMATH DE number 3985346 (Why is no real title available?)
• scientific article; zbMATH DE number 1182959 (Why is no real title available?)
• scientific article; zbMATH DE number 3721037 (Why is no real title available?)
• scientific article; zbMATH DE number 179020 (Why is no real title available?)
• scientific article; zbMATH DE number 1156646 (Why is no real title available?)
• scientific article; zbMATH DE number 863489 (Why is no real title available?)
• scientific article; zbMATH DE number 867700 (Why is no real title available?)
• scientific article; zbMATH DE number 3206365 (Why is no real title available?)
• scientific article; zbMATH DE number 3300652 (Why is no real title available?)
• Maximal sets of numbers not containing k+1 pairwise coprime integers
• On cycles in the coprime graph of integers
• On extremal sets without coprimes
• On vertex numbering of certain classes of graphs
• Primality of trees
• Prime labeling of graphs
• Prime labelings of bipartite generalized Petersen graphs and other prime cubic bipartite graphs
• Sets of integers and quasi-integers with pairwise common divisor

Cited in

(7)

• Coprime index of a graph
• Hamiltonicity in prime sum graphs
• Correction to: ``Every cubic bipartite graph has a prime labeling except \(K_{3,3}\)
• scientific article; zbMATH DE number 2076922 (Why is no real title available?)
• Subgraphs of coprime graphs on sets of consecutive integers
• Minimum coprime graph labelings
• On generalized coprime graphs

This page was built for publication: Hamiltonicity of a coprime graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2053700)