Alphabet Overlap Graph

If a graph G= G(k,d,s) has the vertex set V={v : v= (v1,…vk); vi E {1,2,…,d} (1<= i <= k)}, then it is understood to be an alphabet overlap graph with the set of all k-letter words over an alphabet of size d. Alphabet overlap graph can be used to generalize the concept of DNA graphs. The k raised to the power of n vertices are labeled with the sequences of length n from an alphabet of size k in the alphabet overlap graph. Two vertices are adjacent if the corresponding tags are the same. Through research, the Hamiltonicity, chromatic number, planarity, domination number can be determined through an alphabet overlap graph.

Finding the chromatic number of the graph G= G(k,d,s) will be my contribution to the research. Chromatic number is defined as the minimum number of colors needed to properly color the graph. Throughout the graph a vertex may be one color as long as it’s not connected to another vertex with the same color. The chromatic number of G (k,d,s) is given by X (G (k,d,s))=d^k-2t + d^t if the tag length t<= k/2. I will be finding the chromatic number as k >= 3, and pinpointing the results when k=3, 4, and 5. After finding their chromatic numbers, and proving they are correct, I will produce a method to properly color the graph.


Please contact Glenda if there are any questions, comments, or suggestions.



Back