Some Properties of Prime Graphs

Abstract

In this paper, we give some necessary conditions for a prime graph. We also present some new families of prime graphs such as $K_n\odot K_1$ is prime if and only if $n\le 7$, $K_n\odot \overline{K_2}$ is prime if and only if $n\le 16$, and $K_m\bigcup S_n$ is prime if and only if $\pi (m+n-1)\ge m$. We also show that a prime graph of order greater than or equal to $20$ has a nonprime complement.