Clique Partitions of Graphs with Large Minimum Degree

Dr. Grant Zhang

Department of Mathematical Sciences
University of Alabama in Huntsville

January 26, 2001

Abstract

Let G be a graph of order v and minimum degree δ. A clique in G is a complete subgraph of G. A collection C of cliques in G is called a clique partition of every edge of G is contained in exactly one member of C. The clique partition number of G, denoted cp(G), is the minimum cardinality among all clique partitions of G.

A finite linear space (FLS) consists of a finite set P of points and a collection of subsets of P called lines such that

1. Given any two points, there exists a unique line that contains them both.
2. Each line contains at least two and at most |P| − 1 points.

A finite projective plane (of parameter n) is an FLS such that each line contains exactly n + 1 points and each point is contained in n + 1 lines.

In this talk, we will discuss cp(G) in terms of the order and the minimum degree of G. For a graph G with large minimum degree, it turns out that finite projective planes, weighing matrices, and other algebraic techniques play a crucial role in determining cp(G). The asymptotic behavior of cp(G) when v − δ is small is also explored.