Back to search

East Tennessee State University

On the chromatic number of the <em>AO</em>(2, <em>k </em>, <em>k</em>-1) graphs.

Abstract

dc:description.abstract

The alphabet overlap graph is a modification of the well known de Bruijn graph. De Bruijn graphs have been highly studied and hence many properties of these graphs have been determined. However, very little is known about alphabet overlap graphs. In this work we determine the chromatic number for a special case of these graphs.We define the alphabet overlap graph by G = AO(a, k, t, where a, k and t are positive integers such that 0 ≤ t ≤ k. The vertex set of G is the set of all k-letter sequences over an alphabet of size a. Also there is an edge between vertices u, v if and only if the last t letters in u match the first t letters in v or the first t letters in u match the last t letters in v. We consider the chromatic number for the AO(a, k, t graphs when k > 2, t = k - 1 and a = 2.

Degree

thesis:*
Name thesis:degree_name
MS (Master of Science)
Level thesis:degree_level
Thesis - unrestricted
Discipline thesis:degree_discipline
Mathematical Sciences
Year dc:date.issued
2006

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Arora, Navya

Subjects

dc:subject × 5

Rights

dc:rights
Statement dc:rights
  • Copyright by the authors.

Identifiers

dc:identifier.*
Repository record dc:identifier
https://dc.etsu.edu/etd/2214

Chain of custody

source
Harvested from
East Tennessee State University
Base URL
dc.etsu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Arora, Navya. On the chromatic number of the <em>AO</em>(2, <em>k </em>, <em>k</em>-1) graphs.. Thesis - unrestricted thesis, 2006. https://dc.etsu.edu/etd/2214