On Completely Positive Graphs and Their Complements

In this paper we establish two results concerning completely positive graphs and their complements: (1) The complement of a completely positive graph on ≥ 9 vertices is not completely positive. (2) The spectral radius of the adjacency matrix of a completely positive graph on ≥ 6 vertices is at most . We show that (1) is best possible without additional assumptions. The proofs of (1) and (2) rely on a known fact of extremal graph theory which we state in the language of completely positive graphs and furnish with a proof: The size of a completely positive graph on ≥ 6 vertices is at most . We also give another short proof of (1), under the additional assumption that ≥ 17