Abstract

Let $G_{n}=(V,E)$ be an undirected simple graph, whose vertex set comprises of the natural numbers which are less than $n$ but not relatively prime to $n$ and two distinct vertices $u,v \in V$ are adjacent if and only if $\gcd(u,v)>1$. Connectedness, completeness, minimum degree, maximum degree, independence number, domination number and Eulerian property of the graph $G_n$ are studied in this paper.

Keywords and Phrases

Clique, connected graph, complete graph, prime counting function.

A.M.S. subject classification

05C07, 05C45, 05C69, 11A05.

.....