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 circle dot K-i is prime if and only if n <= 7, K-n circle dot K-2 is prime if and only if n <= 16 and K-m boolean OR S-n is prime if and only if pi(m + n - 1) >= m. We also show that a prime graph of order greater than or equal to 20 has a nonprime complement.