We study the palindromic complexity of infinite words , the fixed points of the substitution over a binary alphabet, , , with , which are canonically associated with quadratic non-simple Parry numbers .
We study the palindromic complexity of infinite words uβ, the fixed points of the substitution over a binary alphabet, φ(0) = 0a1, φ(1) = 0b1, with a - 1 ≥ b ≥ 1, which are canonically associated with quadratic non-simple Parry numbers β.
A simple Parry number is a real number such that the Rényi expansion of is finite, of the form . We study the palindromic structure of infinite aperiodic words that are the fixed point of a substitution associated with a simple Parry number . It is shown that the word contains infinitely many palindromes if and only if . Numbers satisfying this condition are the so-called confluent Pisot numbers. If then is an Arnoux-Rauzy word. We show that if is a confluent Pisot number then...
In the present work, we investigate real numbers whose sequence of partial quotients enjoys some combinatorial properties involving the notion of palindrome. We provide three new transendence criteria, that apply to a broad class of continued fraction expansions, including expansions with unbounded partial quotients. Their proofs heavily depend on the Schmidt Subspace Theorem.
A set T ⊆ L is a Parikh test set of L if c(T) is a test set of c(L). We give a characterization of Parikh test sets for arbitrary language in terms of its Parikh basis, and the coincidence graph of letters.
We show for every k ≥ 1 that the binomial tree of order 3k has a vertex-coloring with 2k+1 colors such that every path contains some color odd number of times. This disproves a conjecture from [1] asserting that for every tree T the minimal number of colors in a such coloring of T is at least the vertex ranking number of T minus one.
A parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let χₚ(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds χ(G) ≤ χₚ(G) ≤ |V(G)|-α(G)+1, where χ(G) and α(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for trees. Namely, if T is a tree with diameter diam(T) and radius rad(T),...
Given graphs G and H, a mapping f:V(G) → V(H) is a homomorphism if (f(u),f(v)) is an edge of H for every edge (u,v) of G. In this paper, we initiate the study of computational complexity of locally injective homomorphisms called partial covers of graphs. We motivate the study of partial covers by showing a correspondence to generalized (2,1)-colorings of graphs, the notion stemming from a practical problem of assigning frequencies to transmitters without interference. We compare the problems of...
We study the problem of finding an alternating path having given endpoints and passing through a given set of vertices in edge-colored graphs (a path is alternating if any two consecutive edges are in different colors). In particular, we show that this problem in NP-complete for 2-edge-colored graphs. Then we give a polynomial characterization when we restrict ourselves to 2-edge-colored complete graphs. We also investigate on (s,t)-paths through fixed vertices, i.e. paths of length s+t such that...
Blanched-Sadri and Woodhouse in 2013 have proven the conjecture of Cassaigne, stating that any pattern with m distinct variables and of length at least 2m is avoidable over a ternary alphabet and if the length is at least 3 2m−1 it is avoidable over a binary alphabet. They conjectured that similar theorems are true for partial words - sequences, in which some characters are left “blank”. Using method of entropy compression, we obtain the partial words version of the theorem for ternary words
This contribution extends the notions of roots and periodicity to strings of transfinite lengths. It shows that given a transfinite string, either it possesses a unique root or the set of its roots are equivalent in a strong way.
This contribution extends the notions of roots and periodicity to strings of transfinite lengths. It shows that given a transfinite string, either it possesses a unique root or the set of its roots are equivalent in a strong way.