On Simple Graphs Arising from Exponential Congruences
We introduce and investigate a new class of graphs arrived from exponential congruences. For each pair of positive integers a and b, let G(n) denote the graph for which V={0,1,…,n−1} is the set of vertices and there is an edge between a and b if the congruence ax≡b (mod n) is solvable. Let n=p1k1p2k...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2012-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2012/292895 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832568275343507456 |
|---|---|
| author | M. Aslam Malik M. Khalid Mahmood |
| author_facet | M. Aslam Malik M. Khalid Mahmood |
| author_sort | M. Aslam Malik |
| collection | DOAJ |
| description | We introduce and investigate a new class of graphs arrived from exponential congruences. For each pair of positive integers a and b, let G(n) denote the graph for which V={0,1,…,n−1} is the set of vertices and there is an edge between a and b if the congruence ax≡b (mod n) is solvable. Let n=p1k1p2k2⋯prkr be the prime power factorization of an integer n, where p1<p2<⋯<pr are distinct primes. The number of nontrivial self-loops of the graph G(n) has been determined and shown to be equal to ∏i=1r(ϕ(piki)+1). It is shown that the graph G(n) has 2r components. Further, it is proved that the component Γp of the simple graph G(p2) is a tree with root at zero, and if n is a Fermat's prime, then the component Γϕ(n) of the simple graph G(n) is complete. |
| format | Article |
| id | doaj-art-27cbec7f91ac41edaadf1d0e07494810 |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2012-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-27cbec7f91ac41edaadf1d0e074948102025-02-03T00:59:22ZengWileyJournal of Applied Mathematics1110-757X1687-00422012-01-01201210.1155/2012/292895292895On Simple Graphs Arising from Exponential CongruencesM. Aslam Malik0M. Khalid Mahmood1Department of Mathematics, University of the Punjab, Lahore 54590, PakistanDepartment of Mathematics, University of the Punjab, Lahore 54590, PakistanWe introduce and investigate a new class of graphs arrived from exponential congruences. For each pair of positive integers a and b, let G(n) denote the graph for which V={0,1,…,n−1} is the set of vertices and there is an edge between a and b if the congruence ax≡b (mod n) is solvable. Let n=p1k1p2k2⋯prkr be the prime power factorization of an integer n, where p1<p2<⋯<pr are distinct primes. The number of nontrivial self-loops of the graph G(n) has been determined and shown to be equal to ∏i=1r(ϕ(piki)+1). It is shown that the graph G(n) has 2r components. Further, it is proved that the component Γp of the simple graph G(p2) is a tree with root at zero, and if n is a Fermat's prime, then the component Γϕ(n) of the simple graph G(n) is complete.http://dx.doi.org/10.1155/2012/292895 |
| spellingShingle | M. Aslam Malik M. Khalid Mahmood On Simple Graphs Arising from Exponential Congruences Journal of Applied Mathematics |
| title | On Simple Graphs Arising from Exponential Congruences |
| title_full | On Simple Graphs Arising from Exponential Congruences |
| title_fullStr | On Simple Graphs Arising from Exponential Congruences |
| title_full_unstemmed | On Simple Graphs Arising from Exponential Congruences |
| title_short | On Simple Graphs Arising from Exponential Congruences |
| title_sort | on simple graphs arising from exponential congruences |
| url | http://dx.doi.org/10.1155/2012/292895 |
| work_keys_str_mv | AT maslammalik onsimplegraphsarisingfromexponentialcongruences AT mkhalidmahmood onsimplegraphsarisingfromexponentialcongruences |