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 $.
Citation: M. Haris Mateen, Muhammad Khalid Mahmmod, Doha A. Kattan, Shahbaz Ali. A novel approach to find partitions of $ Z_{m} $ with equal sum subsets via complete graphs[J]. AIMS Mathematics, 2021, 6(9): 9998-10024. doi: 10.3934/math.2021581
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 $.
| [1] | A. Adler, J. Coury, The theory of numbers: A text and source book of problems, Boston: Jones and Bartlett, 1995. |
| [2] |
A. T. Balaban, Applications of graph theory in chemistry, J. Chem. Inf. Comput. Sci., 25 (1985), 334-43. doi: 10.1021/ci00047a033
|
| [3] |
K. Balasubramanian, Graph theoretical perception of molecular symmetry, Chem. Phys. Lett., 232 (1995), 415-423. doi: 10.1016/0009-2614(94)01382-6
|
| [4] | N. Deo, Graph theory with applications to engineering and computer science, Courier Dover Publications, 2017. |
| [5] |
F. Dorfler, F. Bullo, Kron reduction of graphs with applications to electrical networks, IEEE Trans. Circuits Syst., 60 (2013), 150-163. doi: 10.1109/TCSI.2012.2215780
|
| [6] | G. H. Hardy, E. M. Wright, An introduction to the theory of numbers, Oxford University Press, 1980. |
| [7] | K. Ireland, M. Rosen, A classical introduction to modern number theory, New York: Springer, 1982. |
| [8] | N. Jafarzadeh, A. Iranmanesh, Application of graph theory to biological problems, Stud. Univ. Babes-Bolyai, Chem., 61 (2016), 9-16. |
| [9] |
Y. Meemark, N. Wiroonsri, The quadratic digraph on polynomial rings over finite fields, Finite Fields Appl., 16 (2010), 334-346. doi: 10.1016/j.ffa.2010.05.004
|
| [10] | M. K. Mahmood, F. Ahmad, An informal enumeration of squares of $2^k$ using rooted trees arising from congruences, Utilitas Math., 105 (2017), 41-51. |
| [11] |
M. K. Mahmood, F. Ahmad, A classification of cyclic nodes and enumerations of components of a class of discrete graphs, Appl. Math. Inf. Sci., 9 (2015), 103-112. doi: 10.12785/amis/090115
|
| [12] | M. H. Mateen, M. K. Mahmood, Power digraphs associated with the congruence $x^{n} \equiv y(\text{mod} m)$, Punjab Univ. J. Math., 51 (2019), 93-102. |
| [13] |
M. H. Mateen, M. K. Mahmmod, D. Alghazzawi, J. B. Liu, Structures of power digraphs over the congruence equation $ x^ p\equiv y\; (\text{mod}\; m) $ and enumerations, AIMS Math., 6 (2021), 4581-4596. doi: 10.3934/math.2021270
|
| [14] | M. H. Mateen, M. K. Mahmood, A new approch for the enumeration of components of digraphs over the quadratic maps, J. Prime Res. Math., 16 (2020), 56-66. |
| [15] | M. H. Mateen, M. K. Mahmood, S. Ali, Importance of power digraph in computer science, 2019 International Conference on Innovative Computing (ICIC), (2019), 1-16. Available from: https://ieeexplore.ieee.org/document/8966737. |
| [16] |
D. Namlı, Some results on cubic residues, Int. J. Algebra, 9 (2015), 245-249. doi: 10.12988/ija.2015.5525
|
| [17] | K. H. Rosen, Elementary number theory and its application, Addison-Wesley Publishing Company, 1984. |
| [18] |
T. D. Rogers, The graph of the square mapping on the prime fields, Discrete Math., 148 (1996), 317-324. doi: 10.1016/0012-365X(94)00250-M
|
| [19] |
L. Somer, Křížek, Structure of digraphs associated with quadratic congruences with composite moduli, Discrete Math., 306 (2006), 2174-2185. doi: 10.1016/j.disc.2005.12.026
|
| [20] | Y. J. Wei, G. H. Tang, The square mapping graphs of the ring $Z_{n}[i]$, J. Math., 36 (2016), 676-682. |
| [21] | S. Ali, M. K. Mahmood, M. H. Mateen, New labeling algorithm on various classes of graphs with applications, 2019 International Conference on Innovative Computing (ICIC), (2019), 1-6. Available from: https://ieeexplore.ieee.org/document/8966729. |
| [22] |
S. Ali, M. K. Mahmmod, R. M. Falcón, A paradigmatic approach to investigate restricted hyper totient graphs, AIMS Math., 6 (2021), 3761-3771. doi: 10.3934/math.2021223
|
| [23] | M. K. Mahmood, S. Ali, On super totient numbers, with applications and algorithms to graph labeling, Ars Comb., 143 (2019), 29-37. |
| [24] | S. Ali, M. K. Mahmood, K. P. Shum, Novel classes of integers and their applications in graph labeling, Hacettepe J. Math. Stat., 1 (2021), 1-17. |
Figures(5)
M. Haris Mateen, Muhammad Khalid Mahmmod, Doha A. Kattan, Shahbaz Ali. A novel approach to find partitions of $ Z_{m} $ with equal sum subsets via complete graphs[J]. AIMS Mathematics, 2021, 6(9): 9998-10024. doi: 10.3934/math.2021581
DownLoad: