TOPICS
Search

Intersection Number

The intersection number omega(G), also called the edge clique cover number, clique edge cover number, R-content, or (confusingly) clique cover number, of a given graph G is the minimum number of cliques needed to cover all of the edges of G (i.e., whose edges form an edge cover of G). As a result of this definition, only maximal cliques need be considered.

A connected graph G with vertex count n and edge count m satisfies

omega(G)<=min(m,|_1/4n^2_|)
(1)

(Harary 1994, pp. 19-20).

The triangle giving the numbers of simple unlabeled graphs with intersection number k=0, 1, ..., |_n^2/4_| for n=1, 2, ..., is given by

1 1,1 1,2,1 1,3,4,2,1 1,4,9,10,7,2,1 1,5,17,36,46,30,14,4,2,1 1,6,28,97,219,281,226,116,45,18,5,1,1
(2)

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

1 0,1 0,1,1 0,1,2,2,1 0,1,4,7,6,2,1 0,1,6,22,36,27,13,4,2,1 0,1,9,53,161,242,209,111,43,17,5,1,1
(3)

(OEIS A355755).

For a graph with n>3 vertices and m edges, omega(G)=m iff G 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 K_n. While Choudamand and Parthasarathy (1975), Thomas (2004, p. 28), and Jinnah and Mathew (2017) seem to give

omega(K_n)=[1+log_2n],
(4)

the fact that the graph K_n is an edge cover of itself requires that omega(K_n)=1 for n>1.

See also

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

Explore with Wolfram|Alpha

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

Subject classifications