Bounding the CP-rank by graph parameters

Abstract

The cp-rank of a graph G, cpr(G), is the maximum cp-rank of a completely positive matrix with graph G. One obvious lower bound on cpr(G) is the (edge-) clique covering number, cc(G), i.e., the minimal number of cliques needed to cover all of Gâs edges. It is shown here that for a connected graph G, cpr(G) = cc(G) if and only if G is triangle free and not a tree. Another lower bound for cpr(G) is tf(G), the maximum size of a triangle free subgraph of G. We consider the question of when does the equality cpr(G) = tf(G) hold.