Some Properties of Alphabet Overlap Graphs

Details Some Properties of Alphabet Overlap Graphs Some Properties of Alphabet Overlap Graphs

2005-10-05

arxiv.org/abs/math/0510094v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Some Properties of Alphabet Overlap Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Some Properties of Alphabet Overlap Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Some Properties of Alphabet Overlap Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-250326