Student: | Nechama Florans |
---|---|

Office: | Core 448 |

School: | Kean University |

E-mail: | floransn@kean.edu |

Project: | Edge Clique Covers of Complete Multipartite Graphs |

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.

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

- First Presentation
- Second Presentation
- (Please email me for the full presentation.)