DIMACS
DIMACS REU 2012

General Information

Student: Nechama Florans
Office: Core 448
School: Kean University
E-mail: floransn@kean.edu
Project: Edge Clique Covers of Complete Multipartite Graphs

Project Description

A clique S is a partition of a graph G such that any vertex contained in S is connected. A vertex clique cover (or edge clique cover) is a family of cliques S such that any vertex (or edge) is contained in some clique in the family. The vertex clique cover number (or edge clique cover number) is the minimum size of vertex clique covers (or edge clique covers) of a graph G. A multipartite graph is a graph G where V(G) is subdivided into different partitions in which no edges exist within any one partition. A complete multipartite graph is a multipartite graph in which each vertex is connected to every other vertex that is not in the same partition as it.

The vertex clique cover number of a complete multipartite graph is known to be the vertex size of the largest partition. The edge clique cover number of a complete multipartite graph however, is not completely known. It is a well-known NP-hard problem in computer science and graph theory. Several bounds on the edge clique cover have been determined but I hope to create more precise bounds so that we can get a closer value for the edge clique cover number of any complete multipartite graph. I will look at cases where the vertex sets in each partition are equal. I will also analyze what happens when there are only 3 or 4 partitions. The edge clique cover number can be computed using mutually orthogonal Latin Squares, where each cell forms another clique in a complete multipartite graph; so I will use Latin squares in my research to try and answer some questions.


Weekly Log

Week 1:
Completed presentation on research question and proved a case for the edge clique cover of a tripartite graph
Week 2:
Worked on edge clique covers for complete multipartite graphs with 4 and 5 partite sets
Week 3:
Wrote up a proof for the edge clique cover of a five-partitioned complete multipartite graph, came up with an algorithm for finding the edge clique cover when the partitions are not all of the same size.
Week 4:
Developed and proved two algorithms for finding an edge clique cover of a tripartite graph using Latin Squares.
Week 5:
Revised proofs for algorithms and edge clique covers of complete multipartite graphs.
Week 6:
Completed final presentation and revised manuscript.
Week 7:
Looked over and edited manuscript in more detail, worked on applying one of the algorithms to tetrapartite cases and greater, presented research results.
Week 8:
Finished up final report, tried proving my algorithm for graphs with partite sets greater than 3, found a counterexample to the algorithm for a six-partite graph.

Presentations


Additional Information

My Mentor: Dr. Boram Park