TOPICS

# Intersection Number

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.

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 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).

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 .

Clique Covering Number, Edge Cover, Erdős Sequence, Graph Intersection

## Explore with Wolfram|Alpha

More things to try:

## References

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.

## Referenced on Wolfram|Alpha

Intersection Number

## Cite this as:

Weisstein, Eric W. "Intersection Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/IntersectionNumber.html