VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • On a generalization of Thue sequences [Elektronski vir]
    Kranjc, Jaka, 1988- ...
    A sequence is Thue or nonrepetitive if it does not contain a repetition of any length. We consider a generalization of this notion. A j-subsequence of a sequence S is a subsequence in which two ... consecutive terms are at indices of difference j in S. A k-Thue sequence is a sequence in which every j-subsequence, for 1 <= j <= k, is also Thue. It was conjectured that k+2 symbols are enough to construct an arbitrarily long k-Thue sequence and shown that the conjecture holds for k = 2,3 and 5. In this paper we present a construction of k-Thue sequences on 2k symbols, which improves the previous bound of 2k + 10k^(1/2). Additionally, we define cyclic k-Thue sequences and present a construction of such sequences of arbitrary lengths when k = 2 using four symbols, with three exceptions. As a corollary, we obtain tight bounds for total Thue colorings of cycles. We conclude the paper with some open problems.
    Vir: The Electronic journal of combinatorics [Elektronski vir]. - ISSN 1077-8926 (Vol. 22, Iss. 2, 2015, str. 1-14)
    Vrsta gradiva - e-članek
    Leto - 2015
    Jezik - angleški
    COBISS.SI-ID - 2048289538

    Povezava(-e):

    http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p33

Vnos na polico