Some Properties of Alphabet Overlap Graphs
Some Properties of Alphabet Overlap Graphs
复制标题
DOI：
--
复制
发表时间：
2005-10
期刊：
影响因子：
--
通讯作者：
A. Godbole;Debra J. Knisley;R. Norwood
中科院分区：
文献类型：
--
作者：
A. Godbole;Debra J. Knisley;R. Norwood
考虑一个图G = G（k，d，s），其顶点集V = {v：v =（v1，. . .，vk）; vi ∈ {1，2，. . .，d}（1 ≤ i ≤ k）}，在大小为d的“字母表”上所有k个字母的“单词”的集合。此外，顶点v 6 w之间有一条边，当且仅当v的最后k − s个字母与w的前k − s个字母相同，或者v的前k − s个字母与w的最后k − s个字母相同。本文证明了G对所有非平凡参数都是Hamilton的，并得到了当s ≥ k/2时G的色数的精确值和当s < k/2时G的色数的界.
Consider a graph G = G(k, d, s) with the vertex set V = {v : v = (v1, . . . , vk); vi ∈ {1,2, . . . , d}(1 ≤ i ≤ k)}, the set of all k-letter “words” over an “alphabet” of size d. Furthermore, there will be an edge between vertices v 6 w iff the last k − s letters of v are the same as the first k − s letters of w or the first k − s letters of v are the same as the 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 ≥ k/2 and bounds on its chromatic number when s < k/2.