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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

On the independence number of a variant of the divisor graph

Springer Link (Chiba Institute of Technology)
Limits and Structures in Graph Theory
article

On the independence number of a variant of the divisor graph

article en

Abstract

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.

Springer Link (Chiba Institute of Technology)
Institute of Applied Dermatology (IN)
Openalex Percentile: Top 25%
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.