Non-Coprime Graph of Integers

N. Mohamed Rilwan; M. Mohamed Sameema; A. Roobin Oli

doi:https://doi.org/10.14445/22315373/IJMTT-V66I2P513

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 66 | Issue 2 | Year 2020 | Article Id. IJMTT-V66I2P513 | DOI : https://doi.org/10.14445/22315373/IJMTT-V66I2P513

Non-Coprime Graph of Integers

N. Mohamed Rilwan, M. Mohamed Sameema, A. Roobin Oli

Citation :

N. Mohamed Rilwan, M. Mohamed Sameema, A. Roobin Oli, "Non-Coprime Graph of Integers," International Journal of Mathematics Trends and Technology (IJMTT), vol. 66, no. 2, pp. 116-120, 2020. Crossref, https://doi.org/10.14445/22315373/IJMTT-V66I2P513

Abstract

In this paper, we introduce a new concept of graph named as non-coprime graph of integers. A non-coprime graph of integers, denoted by Γ(n), is arrived from an integer set X = { 1,2......,n} whereas the vertex set V(G) =X\Y where Y = { x : gcd(x,y) = 1 for every y ε X } and the edge set E(G) = {(x,y) : x,y,ε X and gcd(x,y) ≠ 1 }. In this paper, we analyzed some basic properties of the non-coprime graph of integers such as circumference, girth, clique, chromatic number and also prove that the bounds of the domination number, independence number and independent domination number is sharp.

Keywords

non-coprime graph, domination, Hamiltonian cycle, semi perfect

References

[1] S. Mutharasu, N. Mohamed Rilwan, M. K. Angel Jebitha, and T. Tamizh Chelvam, “On Generalized Coprime Graphs”, Iranian Journal of Mathematical Sciences and Informatics, Vol. 9, No. 2, pp. 1-6 (2014).
[2] Paul Erdos, Gabor N. Sarkozy, “On Cycles in the Coprime graph of integers”, Electron. J. Combin., 4 (2), (1997), #R8.
[3] Gabor N. Sarkozy, “Complete tripartite subgraphs in the coprime graph of integers”, Discrete Math., 202, pp. 227-238 (1999).
[4] Paul Erdos, “Remarks in number theory”, IV,(in Hungarian), Mat. Lapok, 13 (1962), 228-225.
[5] Paul Erdos, R. Freud and N. Hegyvari, “Arithmetical properties of permutations of integers”, Acta Math. Acad. Sci. Hung., 41 (1983), 169-176.
[6] Paul Erdos and C. Pomerance , “Mathching the natural numbers upto n with distinct multiples with another interval”, Nederl. Akad. Wetensch. Proc. Ser. A, 83 (1980), 147-161.
[7] R.L. Graham, M. Grotschel, L. Lovasz (editors), “Handbook of combinatorics”, MIT Press
[8] C. Pomerance, “On the longest simple path in the divisor graph”, Congressus Numerantium, 40 (1983), 291-304
[9] E. Saias, “Etude du graphe divisorie”I, Periodica Math. Hung., to appear.
[10] Wayne Goddard and Michael A. Henning, “Independent domination in graphs: A survey and recent results”, Discrete Mathematics 313 (2013) 839-854.
[11] Farzaneh Mansoori, Ahmad Erfanian, and Behnaz Tolue, Non-coprime graph of a finite group, AIP Conf. Proc. 1750, 050017-1 – 050017-9, 21 June 2016.