The 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 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.
For a graph with
vertices and
edges, iff is triangle-free (Harary
1994, p. 19).
Harary (1994, problem 2.26, p. 25) posed the problem of finding the intersection number of a complete graph . While Choudamand and Parthasarathy (1975), Thomas (2004,
p. 28), and Jinnah and Mathew (2017) seem to give
(4)
the fact that the graph is an edge cover of itself requires that for .
Choudamand, S. A. and Parthasarathy, K. R. "On The Intersection Number of Some Graphs." Proc. Indian Nat. Sci. Acad.41,
Part A, No. 3, 307-317, 1975.Erdős, P.; Goodman, A. W.;
and Póa, L. "The Representation of a Graph by Set Intersections."
Canad. J. Math.18, 106-112, 1966.Gross, J. T. and
Yellen, J. Graph
Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, p. 440,
2006.Harary, F. Graph
Theory. Reading, MA: Addison-Wesley, pp. 19-20, 1994.Harary,
F. and Palmer, E. M. Graphical
Enumeration. New York: Academic Press, p. 225, 1973.Harary,
F. and Palmer, E. M. "A Survey of Graph Enumeration Problems." In
A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam:
North-Holland, pp. 259-275, 1973.Jinnah, M. I. and Mathew,
S. C. "Intersection Number of Some Comaximal Graphs." Palestine
J. Math.6, 458-464, 2017.Roberts, F. S. "Applications
of Edge Coverings by Cliques." Disc. Appl. Math.10, 93-109, 1985.Sloane,
N. J. A. Sequences A355754 and A355755 in "The On-Line Encyclopedia of Integer
Sequences."Thomas, C. "A Study of Some Problems in Algebraic
Graph Theory--Graphs Arising from Rings." Ph. D. thesis. Thiruvananthapuram,
India: University of Kerala, March 2004.