Some Necessary and Sufficient Conditions for Diophantine Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917040182263808 |
|---|---|
| author | Seoud, M. A. Elsonbaty, A. Nasr, A. Anwar, M. |
| author_facet | Seoud, M. A. Elsonbaty, A. Nasr, A. Anwar, M. |
| contents | A linear Diophantine equation $ax + by = n$ is solvable if and only if gcd$(a; b)$ divides $n$. A graph $G$ of order $n$ is called Diophantine if there exists a labeling function $f$ of vertices such that gcd$(f(u); f(v))$ divides $n$ for every two adjacent vertices $u; v$ in $G$. In this work, maximal Diophantine graphs on $n$ vertices, $D_n$, are defined, studied and generalized. The independence number, the number of vertices with full degree and the clique number of $D_n$ are computed. Each of these quantities is the basis of a necessary condition for the existence of such a labeling. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_20562 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Some Necessary and Sufficient Conditions for Diophantine Graphs Seoud, M. A. Elsonbaty, A. Nasr, A. Anwar, M. Combinatorics Number Theory A linear Diophantine equation $ax + by = n$ is solvable if and only if gcd$(a; b)$ divides $n$. A graph $G$ of order $n$ is called Diophantine if there exists a labeling function $f$ of vertices such that gcd$(f(u); f(v))$ divides $n$ for every two adjacent vertices $u; v$ in $G$. In this work, maximal Diophantine graphs on $n$ vertices, $D_n$, are defined, studied and generalized. The independence number, the number of vertices with full degree and the clique number of $D_n$ are computed. Each of these quantities is the basis of a necessary condition for the existence of such a labeling. |
| title | Some Necessary and Sufficient Conditions for Diophantine Graphs |
| topic | Combinatorics Number Theory |
| url | https://arxiv.org/abs/2412.20562 |