A novel approach to find partitions of $ Z_{m} $ with equal sum subsets via complete graphs

AIMS Mathematics

M. Haris Mateen¹  Muhammad Khalid Mahmmod¹ 

[1] 1. Department of Mathematics, University of the Punjab, Lahore 54590, Pakistan;

关键词: quadratic residues graph;    complete graph;    ring of integers;   

DOI  :  10.3934/math.2021581

来源: DOAJ

【 摘 要 】

In mathematics and computer sciences, the partitioning of a set into two or more disjoint subsets of equal sums is a well-known NP-complete problem, also referred to as partition problem. There are various approaches to overcome this problem for some particular choice of integers. Here, we use quadratic residue graph to determine the possible partitions of positive integers $ m = 2^{\beta}, q^{\beta}, 2^{\beta}q, $ $ 2q^{\beta}, qp, $ where $ p $, $ q $ are odd primes and $ \beta $ is any positive integer. The quadratic residue graph is defined on the set $ Z_{m} = \{\overline{0}, \overline{1}, \cdots, \overline{m-1}\}, $ where $ Z_{m} $ is the ring of residue classes of $ m $, i.e., there is an edge between $ \overline{x}, $ $ \overline{y}\in Z_{m} $ if and only if $ \overline{x}^{2}\equiv \overline{y}^{2}\; (\text{mod}\; m) $. We characterize these graphs in terms of complete graph for some particular classes of $ m $.

【 授权许可】

Unknown