On the independence number of a variant of the divisor graph
Let $ n=p_1^{n_1} p_2^{n_2} \cdots p_t^{n_t} $ be a positive composite integer with distinct primes p1, …, pt. 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 ni > 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.
Institutions
- Institute of Applied Dermatology (IN)
Publication Details
- Journal
- Springer Link (Chiba Institute of Technology)
- Published
- 2025-12-23
- DOI
- https://doi.org/10.1051/ro/2025145/pdf
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00