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 \leq 7\), \(K_n \odot \overline{K_2}\) is prime if and only if \(n \leq 16\), and \(K_{m}\bigcup S_n\) is prime if and only if \(\pi(m+n-1) \geq m\). We also show that a prime graph of order greater than or equal to \(20\) has a nonprime complement.