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