Non-Coprime Graph of Integers

**MLA Style:**N. Mohamed Rilwan, M. Mohamed Sameema, A. Roobin Oli "Non-Coprime Graph of Integers" International Journal of Mathematics Trends and Technology 66.2 (2020):116-120.

**APA Style: ** N. Mohamed Rilwan, M. Mohamed Sameema, A. Roobin Oli(2020). Non-Coprime Graph of Integers International Journal of Mathematics Trends and Technology, 116-120.

**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.

**Reference**

[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.

**Keywords**

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