Graph Intersection Number

The graph intersection number , also called the edge clique cover number, clique edge cover number, -content, or (confusingly) clique cover number, of a given graph is the smallest size of a set for which is the intersection graph of a family of subsets of , where repeated subsets and the empty set are allowed. Equivalently, it is the minimum number of cliques needed to cover all of the edges of (i.e., whose edges form an edge cover of ). As a result of this definition, only maximal cliques need be considered.

A connected graph with vertex count and edge count satisfies

(1)

(Harary 1994, pp. 19-20).

The triangle giving the numbers of simple unlabeled graphs with graph intersection number , 1, ..., for , 2, ..., is given by

(2)

(OEIS A355754), while the corresponding triangle for connected simple unlabeled graphs is

(3)

(OEIS A355755).

For a graph with vertices and edges, iff is triangle-free (Harary 1994, p. 19).

Under the convention used here, the complete graph is itself a one-clique edge cover, so

(4)

for . If the representing subsets are instead required to be distinct, a different parameter is obtained; for , its value is

(5)

This distinction accounts for the larger value given by Choudamand and Parthasarathy (1975), Thomas (2004, p. 28), and Jinnah and Mathew (2017) in connection with Harary's distinct-set formulation (Harary 1994, problem 2.26, p. 25).