BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
An overlap-free (or β-free) word w over a fixed alphabet Σ is extremal if every word obtained from w by inserting a single letter from Σ at any position contains an overlap (or a factor of exponent at least β, respectively). We find all lengths which admit an extremal overlap-free binary word. For every extended real number β such that 2+≤β≤8/3, we show that there are arbitrarily long extremal β-free binary words.
A square-free word w over a fixed alphabet Σ is extremal if every word obtained from w by inserting a single letter from Σ (at any position) contains a square. Grytczuk et al. recently introduced the concept of extremal square-free word, and demonstrated that there are arbitrarily long extremal square-free ternary words. We find all lengths which admit an extremal square-free ternary word. In particular, we show that there is an extremal square-free ternary word of every sufficiently large length. We also solve the analogous problem for circular words.
Let G be a graph, and let u, v, and w be vertices of G. If the distance between u and w does not equal the distance between v and w, then w is said to resolve u and v. The metric dimension of G, denoted β(G), is the cardinality of a smallest set W of vertices such that every pair of vertices of G is resolved by some vertex of W. The threshold dimension of G, denoted τ(G), is the minimum metric dimension among all graphs H having G as a spanning subgraph. In other words, the threshold dimension of G is the minimum metric dimension among all graphs obtained from G by adding edges. If β(G)=τ(G), then G is said to be irreducible. We give two upper bounds for the threshold dimension of a graph, the first in terms of the diameter, and the second in terms of the chromatic number. As a consequence, we show that every planar graph of order n has threshold dimension O(log2n). We show that several infinite families of graphs, known to have metric dimension 3, are in fact irreducible. Finally, we show that for any integers n and b with 1≤b<n, there is an irreducible graph of order n and metric dimension b.
Let G be a graph, and let u, v, and w be vertices of G. If the distance between u and w does not equal the distance between v and w, then w is said to resolve u and v. The metric dimension of G, denoted β(G), is the cardinality of a smallest set W of vertices such that every pair of vertices of G is resolved by some vertex of W. The threshold dimension of a graph G, denoted τ(G), is the minimum metric dimension among all graphs H having G as a spanning subgraph. In other words, the threshold dimension of G is the minimum metric dimension among all graphs obtained from G by adding edges. If β(G)=τ(G), then G is said to be \emph{irreducible}; otherwise, we say that G is reducible. If H is a graph having G as a spanning subgraph and such that β(H)=τ(G), then H is called a threshold graph of G. The threshold dimension of a graph is expressed in terms of a minimum number of strong products of paths that admits a certain type of embedding of the graph. A sharp upper bound for the threshold dimension of trees is established. It is also shown that the irreducible trees are precisely those of metric dimension at most 2. Moreover, if T is a tree with metric dimension 3 or 4, then T has threshold dimension 2. It is shown, in these two cases, that a threshold graph for T can be obtained by adding exactly one or two edges to T, respectively. However, these results do not extend to trees with metric dimension 5, i.e., there are trees of metric dimension 5 with threshold dimension exceeding 2.
For a rational number r such that 1<r≤2, an undirected r-power is a word of the form xyx′, where the word x is nonempty, the word x′ is in {x,xR}, and we have ∣xyx′∣/∣xy∣=r. The undirected repetition threshold for k letters, denoted $\mbox{URT}(k)$, is the infimum of the set of all r such that undirected r-powers are avoidable on k letters. We first demonstrate that $\mbox{URT}(3)=\tfrac{7}{4}$. Then we show that $\mbox{URT}(k)\geq \tfrac{k-1}{k-2}$ for all k≥4. We conjecture that $\mbox{URT}(k)=\tfrac{k-1}{k-2}$ for all k≥4, and we confirm this conjecture for k∈{4,5,…,21}. We then consider related problems in pattern avoidance; in particular, we find the undirected avoidability index of every binary pattern. This is an extended version of a paper presented at WORDS 2019, and it contains new and improved results.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.