{"id":{"repo_id":"etsu","oai_identifier":"oai:dc.etsu.edu:etd-3578"},"canonical_url":"https://search.ndltd.org/etd/etsu/oai:dc.etsu.edu:etd-3578","repository":{"repo_id":"etsu","name":"East Tennessee State University","base_url":"https://dc.etsu.edu/do/oai/"},"display":{"title":"On the chromatic number of the <em>AO</em>(2, <em>k </em>, <em>k</em>-1) graphs.","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.","abstract_html":"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 &gt; 2, t = k - 1 and a = 2.","abstract_has_math":false,"creators":["Arora, Navya"],"institution":null,"degree_name":"MS (Master of Science)","degree_level":"Thesis - unrestricted","degree_discipline":"Mathematical Sciences","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2006,"date_issued":"2006-05-06T07:00:00Z","date_published":"2006-05-06T07:00:00Z","updated_at":"2026-11-19T07:53:44Z","subjects":["de Bruijn graph","chromatic number","Discrete Mathematics and Combinatorics","Mathematics","Physical Sciences and Mathematics"],"languages":[],"rights":["Copyright by the authors."],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://dc.etsu.edu/etd/2214","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://dc.etsu.edu/etd/2214","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":"https://dc.etsu.edu/context/etd/article/3578/viewcontent/AroraN042606f.pdf","download_label":"Download PDF","download_source":"dc:identifier","access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://dc.etsu.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adc.etsu.edu%3Aetd-3578","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Arora, Navya"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2006-05-06T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematical Sciences"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis - unrestricted"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS (Master of Science)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["de Bruijn graph","chromatic number","Discrete Mathematics and Combinatorics","Mathematics","Physical Sciences and Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["Copyright by the authors."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://dc.etsu.edu/context/etd/article/3578/viewcontent/AroraN042606f.pdf","https://dc.etsu.edu/etd/2214"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["On the chromatic number of the <em>AO</em>(2, <em>k </em>, <em>k</em>-1) graphs."]}]}],"canonical_facts":{"dc:creator":["Arora, Navya"],"dc:date.issued":["2006-05-06T07:00:00Z"],"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."],"dc:identifier":["https://dc.etsu.edu/context/etd/article/3578/viewcontent/AroraN042606f.pdf","https://dc.etsu.edu/etd/2214"],"dc:rights":["Copyright by the authors."],"dc:subject":["de Bruijn graph","chromatic number","Discrete Mathematics and Combinatorics","Mathematics","Physical Sciences and Mathematics"],"dc:title":["On the chromatic number of the <em>AO</em>(2, <em>k </em>, <em>k</em>-1) graphs."],"thesis:degree_discipline":["Mathematical Sciences"],"thesis:degree_level":["Thesis - unrestricted"],"thesis:degree_name":["MS (Master of Science)"]},"updated_at":"2026-11-19T07:53:44Z"}