On divisibility relation graphs

2025/07/09 by Jonathan L. Merzel, Ján Mináč, Merzel, Jonathan L. +5
Computer Science · Mathematics · #05C25 #05C50 #06A07 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2507.06873

openalex publication_date 2025/07/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For each positive integer n, we define the divisibility relation graph D_n whose vertex set is the set of divisors of n, and in which two vertices are adjacent if one is a divisor of the other. This type of graph is a special case of graphs associated with a partial order, which have been widely studied in the literature. In this work, we determine various graph-theoretic invariants of divisibility relation graphs, such as their clique and independence numbers, and their planarity. We also discuss various spectral properties that are discovered by our numerical experiments.

Citations

• On gcd-graphs over finite rings
• Joins of normal matrices, their spectrum, and applications
• Counting primitive subsets and other statistics of the divisor graph of \1,2, … n\
• On path partitions of the divisor graph
• A Cameron and Erdös conjecture on counting primitive sets

Related

• Divisor graphs have arbitrary order and size
• Graph Invariants Based on the Divides Relation and Ordered by Prime Signatures
• Some Properties of Order-Divisor Graphs of Finite Groups
• Patterns of primes and composites on divisibility graph
• Bipartite divisor graphs for integer subsets