On computing the distinguishing numbers of trees and forests.
On conjugacy of languages
We say that two languages and are conjugates if they satisfy the conjugacy equation for some language . We study several problems associated with this equation. For example, we characterize all sets which are conjugated a two-element biprefix set , as well as all two-element sets which are conjugates.
On Conjugacy of Languages
We say that two languages X and Y are conjugates if they satisfy the conjugacy equationXZ = ZY for some language Z. We study several problems associated with this equation. For example, we characterize all sets which are conjugated via a two-element biprefix set Z, as well as all two-element sets which are conjugates.
On critical exponents in fixed points of -uniform binary morphisms
Let be an infinite fixed point of a binary -uniform morphism , and let be the critical exponent of . We give necessary and sufficient conditions for to be bounded, and an explicit formula to compute it when it is. In particular, we show that is always rational. We also sketch an extension of our method to non-uniform morphisms over general alphabets.
On Critical exponents in fixed points of k-uniform binary morphisms
Let w be an infinite fixed point of a binary k-uniform morphism f, and let Ew be the critical exponent of w. We give necessary and sufficient conditions for Ew to be bounded, and an explicit formula to compute it when it is. In particular, we show that Ew is always rational. We also sketch an extension of our method to non-uniform morphisms over general alphabets.
On external-memory planar depth first search.
On extremal properties of the Fibonacci word
We survey several quantitative problems on infinite words related to repetitions, recurrence, and palindromes, for which the Fibonacci word often exhibits extremal behaviour.
On -wise arc forwarding index and wavelength allocations in faulty all-optical hypercubes
Motivated by the wavelength division multiplexing in all-optical networks, we consider the problem of finding an optimal (with respect to the least possible number of wavelengths) set of internally node disjoint dipaths connecting all pairs of distinct nodes in the binary -dimensional hypercube, where . This system of dipaths constitutes a routing protocol that remains functional in the presence of up to faults (of nodes and/or links). The problem of constructing such protocols for general...
On Galois correspondences for one-place functions with delays.
On -pairable graphs from trees
The concept of the -pairable graphs was introduced by Zhibo Chen (On -pairable graphs, Discrete Mathematics 287 (2004), 11–15) as an extension of hypercubes and graphs with an antipodal isomorphism. In the same paper, Chen also introduced a new graph parameter , called the pair length of a graph , as the maximum such that is -pairable and if is not -pairable for any positive integer . In this paper, we answer the two open questions raised by Chen in the case that the graphs involved...
On linear layouts of graphs.
On locating a single path-like facility in a general graph
On location problems on fuzzy graphs.
Location problems concern a wide set of fields where it is usually assumed that exact data are known. However, in real applications, the location of the facility considered can be full of linguistic vagueness, that can be appropriately modeled using networks with fuzzy values. In that way arise Fuzzy Location Problems; this paper deals with their general formulation and the description solution methods. Namely we show the variety of problems that can be considered in this context and, for some of...
On low-complexity bi-infinite words and their factors
In this paper we study bi-infinite words on two letters. We say that such a word has stiffness if the number of different subwords of length equals for all sufficiently large. The word is called -balanced if the numbers of occurrences of the symbol a in any two subwords of the same length differ by at most . In the present paper we give a complete description of the class of bi-infinite words of stiffness and show that the number of subwords of length from this class has growth order...
On maximal finite antichains in the homomorphism order of directed graphs
We show that the pairs where T is a tree and its dual are the only maximal antichains of size 2 in the category of directed graphs endowed with its natural homomorphism ordering.
On minimal words with given subword complexity.
On Minimum and Maximum Spanning Trees of Linearly Moving Points.
On multiperiodic words
In this note we consider the longest word, which has periods p1,...,pn, and does not have the period gcd(p1,...,pn). The length of such a word can be established by a simple algorithm. We give a short and natural way to prove that the algorithm is correct. We also give a new proof that the maximal word is a palindrome.
On multiplicatively dependent linear numeration systems, and periodic points
Two linear numeration systems, with characteristic polynomial equal to the minimal polynomial of two Pisot numbers and respectively, such that and are multiplicatively dependent, are considered. It is shown that the conversion between one system and the other one is computable by a finite automaton. We also define a sequence of integers which is equal to the number of periodic points of a sofic dynamical system associated with some Parry number.
On multiplicatively dependent linear numeration systems, and periodic points
Two linear numeration systems, with characteristic polynomial equal to the minimal polynomial of two Pisot numbers β and γ respectively, such that β and γ are multiplicatively dependent, are considered. It is shown that the conversion between one system and the other one is computable by a finite automaton. We also define a sequence of integers which is equal to the number of periodic points of a sofic dynamical system associated with some Parry number.