Some Properties of Alphabet Overlap Graphs
| dc.creator | Godbole, Anant | |
| dc.creator | Knisley, Debra | |
| dc.creator | Norwood, Rick | |
| dc.date | 2005-10-05 | |
| dc.date.accessioned | 2026-07-07T06:21:09Z | |
| dc.date.available | 2026-07-07T06:21:09Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/math/0510094 | |
| dc.identifier | http://arxiv.org/abs/math/0510094 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/95509 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C15 | |
| dc.title | Some Properties of Alphabet Overlap Graphs | |
| dc.type | text |