Clique Partitions of Graphs with Large Minimum Degree
Dr. Grant Zhang
Department of Mathematical Sciences
University of Alabama in Huntsville
January 26, 2001
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
- Given any two points, there exists a unique line that contains them both.
- 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.
- Hits: 91