On the independence number of a variant of the divisor graph

Department of Mathematics, Government College Kasaragod, Vidyanagar, Kasaragod 671123, India

^* Corresponding author: midhunsklm20@gmail.com

Received: 16 August 2025
Accepted: 21 October 2025

Abstract

Let n = p₁^n₁ p₂^n₂ … p_t^n_t be a positive composite integer with distinct primes p₁, …, p_t. Consider the graph G′_n, introduced by Rather and Ganie [RAIRO-Oper. Res. 59 (2025) 1605–1616], whose vertices are the proper divisors of n and where two vertices are adjacent if and only if they are coprime. A complete description of maximal independent sets in G′_n is obtained via a correspondence with maximal intersecting families of subsets of [t]. This correspondence is applied to determine the independence number for various classes of n, including the square-free case, where the exact value and an explicit formula are established. For general n with at least one exponent n_i > 1, the independence number is expressed in terms of combinatorial properties of intersecting families, yielding a unified approach to both the structural characterization and enumeration of maximal independent sets.