Type: Article
Publication Date: 2022-03-29
Citations: 3
DOI: https://doi.org/10.1155/2022/1587689
In computer science and mathematics, a partition of a set into two or more disjoint subsets with equal sums is a well-known NP-complete problem. This is a hard problem and referred to as the partition problem or number partitioning. In this paper, we solve a particular type of NP-complete problem on the set of all zero-divisors of <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" id="M1"> <a:msub> <a:mrow> <a:mi>Z</a:mi> </a:mrow> <a:mrow> <a:mi>n</a:mi> </a:mrow> </a:msub> </a:math> including zero, where <c:math xmlns:c="http://www.w3.org/1998/Math/MathML" id="M2"> <c:msub> <c:mrow> <c:mi>Z</c:mi> </c:mrow> <c:mrow> <c:mi>n</c:mi> </c:mrow> </c:msub> </c:math> is the ring of residue classes of a positive integer <e:math xmlns:e="http://www.w3.org/1998/Math/MathML" id="M3"> <e:mi>n</e:mi> </e:math> . In this regard, we introduce and investigate quadratic zero-divisor graph in which we build an edge between zero-divisors <g:math xmlns:g="http://www.w3.org/1998/Math/MathML" id="M4"> <g:msub> <g:mrow> <g:mi>z</g:mi> </g:mrow> <g:mrow> <g:mi>i</g:mi> </g:mrow> </g:msub> </g:math> and <i:math xmlns:i="http://www.w3.org/1998/Math/MathML" id="M5"> <i:msub> <i:mrow> <i:mi>z</i:mi> </i:mrow> <i:mrow> <i:mi>j</i:mi> </i:mrow> </i:msub> </i:math> if and only if <k:math xmlns:k="http://www.w3.org/1998/Math/MathML" id="M6"> <k:msubsup> <k:mrow> <k:mi>z</k:mi> </k:mrow> <k:mrow> <k:mi>i</k:mi> </k:mrow> <k:mrow> <k:mn>2</k:mn> </k:mrow> </k:msubsup> <k:mo>≡</k:mo> <k:msubsup> <k:mrow> <k:mi>z</k:mi> </k:mrow> <k:mrow> <k:mi>j</k:mi> </k:mrow> <k:mrow> <k:mn>2</k:mn> </k:mrow> </k:msubsup> <k:mtext> </k:mtext> <k:mfenced open="(" close=")"> <k:mrow> <k:mi mathvariant="normal">mod</k:mi> <k:mtext> </k:mtext> <k:mi>n</k:mi> </k:mrow> </k:mfenced> <k:mo>,</k:mo> <k:mi>i</k:mi> <k:mo>≠</k:mo> <k:mi>j</k:mi> </k:math> . This is denoted as <p:math xmlns:p="http://www.w3.org/1998/Math/MathML" id="M7"> <p:mover accent="true"> <p:mi>G</p:mi> <p:mo stretchy="true">⏞</p:mo> </p:mover> <p:mfenced open="(" close=")"> <p:mrow> <p:mn>2</p:mn> <p:mo>,</p:mo> <p:mi>n</p:mi> </p:mrow> </p:mfenced> </p:math> . We characterize these graphs in term of complete graphs for classes of integers <v:math xmlns:v="http://www.w3.org/1998/Math/MathML" id="M8"> <v:msup> <v:mrow> <v:mn>2</v:mn> </v:mrow> <v:mrow> <v:mi>α</v:mi> </v:mrow> </v:msup> <v:mo>,</v:mo> <v:msup> <v:mrow> <v:mi>p</v:mi> </v:mrow> <v:mrow> <v:mi>α</v:mi> </v:mrow> </v:msup> <v:mo>,</v:mo> <v:msup> <v:mrow> <v:mn>2</v:mn> </v:mrow> <v:mrow> <v:mi>α</v:mi> </v:mrow> </v:msup> <v:mi>p</v:mi> <v:mo>,</v:mo> <v:mn>2</v:mn> <v:msup> <v:mrow> <v:mi>p</v:mi> </v:mrow> <v:mrow> <v:mi>α</v:mi> </v:mrow> </v:msup> </v:math> and <x:math xmlns:x="http://www.w3.org/1998/Math/MathML" id="M9"> <x:mi>p</x:mi> <x:mi>q</x:mi> </x:math> , where <z:math xmlns:z="http://www.w3.org/1998/Math/MathML" id="M10"> <z:mi>α</z:mi> </z:math> is any positive integer and <bb:math xmlns:bb="http://www.w3.org/1998/Math/MathML" id="M11"> <bb:mi>p</bb:mi> <bb:mo>,</bb:mo> <bb:mi>q</bb:mi> </bb:math> are odd primes.