Affordable Access

Some Properties of Alphabet Overlap Graphs

Authors
Type
Preprint
Publication Date
Submission Date
Identifiers
arXiv ID: math/0510094
Source
arXiv
License
Unknown
External links

Abstract

Consider a graph G = G(k,d,s) with vertex set the set of all k-letter words over an alphabet of size d. An edge e = vw is in E iff v is distinct from w and the last(first) k-s letters of v are identical to the first(last) k-s letters of w. In this paper we show that G is Hamiltonian for all non-trivial values of the parameters and obtain exact values for its chromatic number when s is greater than or equal to k/2. We also obtain bounds when the chromatic number is less than k/2.

Statistics

Seen <100 times