This paper considers the existence of short synchronizing words in deterministic finite automata (DFAs). We define two general strategies for generating synchronizing words, and we show that each of these strategies can be applied if and only if a DFA is synchronizable. Furthermore, we show that if a synchronizable DFA is well-structured, then our strategies generate short synchronizing words. The first of our strategies, called the cornering strategy , takes advantage of states in a DFA with properties similar to those of a polytope vertex. The second of our strategies, similar to the cornering strategy and called the f-ordered strategy , takes advantage of a partial order defined on the states of a DFA. We apply our cornering strategy to the class of difference DFAs , whose states form subsets of R d and whose input symbols correspond to translation vectors between states. We show that difference DFAs share many similarities with aperiodic DFAs, and in particular, a difference DFA M has a synchronizing word if and only if it has a universally reachable state. Using the cornering strategy, we also show that under certain conditions, such an n -state DFA M has a synchronizing word of length at most ( n − 1 ) 2 and thereby satisfies Černý’s conjecture. Using the f -ordered strategy, we also show that a synchronizable DFA whose states have a certain partial order that is preserved by a set of short words also has a short synchronizing word, and we consider several consequences of this result. Finally, we consider how the cornering strategy can be applied to the problem of synchronizing the product of two DFAs M 1 , M 2 that share a common alphabet, and we show that the product M 1 × M 2 often has a synchronizing word that is subquadratic in the number of states of M 1 × M 2 .

Let $\Lambda(T)$ denote the set of leaves in a tree $T$. One natural problem is to look for a spanning tree $T$ of a given graph $G$ such that $\Lambda(T)$ is as large as possible. This problem is called maximum leaf number, and it is a well-known NP-hard problem. Equivalently, the same problem can be formulated as the minimum connected dominating set problem, where the task is to find a smallest subset of vertices $D\subseteq V(G)$ such that every vertex of $G$ is in the closed neighborhood of $D$. Throughout recent decades, these two equivalent problems have received considerable attention, ranging from pure graph theoretic questions to practical problems related to the construction of wireless networks. Recently, a similar but stronger notion was defined by Bradshaw, Masařík, and Stacho [ Flexible list colorings in graphs with special degeneracy conditions, in Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), LIPIcs. Leibniz Int. Proc. Inform. 181, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020, article 31]. They introduced a new invariant for a graph $G$, called the robust connectivity and written as $\kappa_\rho(G)$, defined as the minimum value $\frac{|R \cap \Lambda (T)|}{|R|}$ taken over all nonempty subsets $R\subseteq V(G)$, where $T = T(R)$ is a spanning tree on $G$ chosen to maximize $|R \cap \Lambda(T)|$. Large robust connectivity was originally used to show flexible choosability in nonregular graphs. In this paper, we investigate some interesting properties of robust connectivity for graphs embedded in surfaces. We prove a tight asymptotic bound of $\Omega(\gamma^{-\frac{1}{r}})$ for the robust connectivity of $r$-connected graphs of Euler genus $\gamma$. Moreover, we give a surprising connection between the robust connectivity of graphs with an edge-maximal embedding in a surface and the surface connectivity of that surface, which describes to what extent large induced subgraphs of embedded graphs can be cut out from the surface without splitting the surface into multiple parts. For planar graphs, this connection provides an equivalent formulation of a long-standing conjecture of Albertson and Berman [ A conjecture on planar graphs, in Graph Theory and Related Topics, Academic Press, San Diego, CA, 1979, p. 57], which states that every planar graph on $n$ vertices contains an induced forest of size at least $n/2$.

For a given ε > 0, we say that a graph G is ε-flexibly k-choosable if the following holds: for any assignment L of lists of size k on V(G), if a preferred color is requested at any set R of vertices, then at least ε |R| of these requests are satisfied by some L-coloring. We consider flexible list colorings in several graph classes with certain degeneracy conditions. We characterize the graphs of maximum degree Δ that are ε-flexibly Δ-choosable for some ε = ε(Δ) > 0, which answers a question of Dvořák, Norin, and Postle [List coloring with requests, JGT 2019]. We also show that graphs of treewidth 2 are 1/3-flexibly 3-choosable, answering a question of Choi et al. [arXiv 2020], and we give conditions for list assignments by which graphs of treewidth k are 1/(k+1)-flexibly (k+1)-choosable. We show furthermore that graphs of treedepth k are 1/k-flexibly k-choosable. Finally, we introduce a notion of flexible degeneracy, which strengthens flexible choosability, and we show that apart from a well-understood class of exceptions, 3-connected non-regular graphs of maximum degree Δ are flexibly (Δ - 1)-degenerate.

Hamiltonicity of graphs possessing symmetry has been a popular subject of research, with focus on vertex-transitive graphs, and in particular on Cayley graphs. In this paper, we consider the Hamiltonicity of another class of graphs with symmetry, namely covering graphs of trees. In particular, we study the problem for covering graphs of trees, where the tree is a voltage graph over a cyclic group. Batagelj and Pisanski were first to obtain such a result, in the special case when the voltage assignment is trivial; in that case, the covering graph is simply a Cartesian product of the tree and a cycle. We consider more complex voltage assignments, and extend the results of Batagelj and Pisanski in two different ways; in these cases the covering graphs cannot be expressed as products. We also provide a linear time algorithm to test whether a given assignment satisfies these conditions.

We show that in the hierarchical tile assembly model, if there is a producible assembly that overlaps a nontrivial translation of itself consistently (i.e., the pattern of tile types in the overlap region is identical in both translations), then arbitrarily large assemblies are producible. The significance of this result is that tile systems intended to controllably produce finite structures must avoid pattern repetition in their producible assemblies that would lead to such overlap. This answers an open question of Chen and Doty (SODA 2012), who showed that so-called "partial-order" systems producing a unique finite assembly and avoiding such overlaps must require time linear in the assembly diameter. An application of our main result is that any system producing a unique finite assembly is automatically guaranteed to avoid such overlaps, simplifying the hypothesis of Chen and Doty's main theorem.

Let $\nu(G)$ be the maximum number of vertex-disjoint odd cycles of a graph $G$ and $\tau(G)$ the minimum number of vertices whose removal makes $G$ bipartite. We show that $\tau(G)\le 6\nu(G)$ if $G$ is planar. This improves the previous bound $\tau(G)\le 10\nu(G)$ by Fiorini et al. [Math. Program. Ser. B, 110 (2007), pp. 71--91].

The primary objective of this work was to identify those human phosphorylation sites (phosphosites) that are highly conserved in other species as this may reveal functionally important phosphosites. We wondered whether human phosphosites (e.g. tyrosine, serine or threonine) that are known to be activatory upon phosphorylation, are commonly replaced by a glutamic or aspartic acid residues in other species. This type of alteration might mimic constitutive phosphorylation of cognate proteins in other species, which would indicate that phosphorylation of these sites in humans may confer functionality. To investigate this, we developed an algorithm to identify ortholog proteins in different species for each given human phospho-protein and also predict phosphosites in every extracted ortholog cognate protein. The results demonstrate that relatively few human phosphosites are highly conserved; for instance from about 90,000 human phosphosites, about 75% of these were conserved in mammals, but less than 16% were detected in most model organisms. These extremely well conserved phosphosites did not display any increased preponderance for acidic amino acid substitutions. However, we observed that the most conserved functional phosphosites occurred on threonine phosphosites that were found in protein kinases and these were 8-times more likely to be stimulatory than inhibitory.

In this paper we propose a new algorithm to predict the phosphorylation site specificities of 478 human protein kinases based on the primary structures of the catalytic domains of these enzymes. Existing methods deduce the specificity of a protein kinase through the alignment of the amino acid sequences of phospho-sites targeted by the kinase to generate a consensus sequence or they use machine learning models for recognition. However, for most protein kinases few if any substrates have been experimentally identified by protein sequencing and mass spectrometry. In this work, we used mutual information from a training set of over 200 protein kinases consensus phospho-site sequences and predicted amino acid interactions between kinases and their substrate phospho-sites to generate position-specific scoring matrices (PSSM). The results demonstrate that using our algorithm, knowledge of the primary amino acid sequence of the catalytic domain of these kinases is sufficient to predict their phosphorylation sites specificities and their PSSM matrices.

We introduce two variants of proper colorings with imposed partial ordering on the set of colors. One variant shows very close connections to some fundamental problems in graph theory, e.g., directed graph homomorphism and list colorings. We study the border between tractability and intractability for both variants.

Abstract We address the problem of discovering routes in strongly connected planar geometric networks with directed links. Motivated by the necessity for establishing communication in wireless ad hoc networks in which the only information available to a vertex is its immediate neighborhood, we are considering routing algorithms that use the neighborhood information of a vertex for routing with constant memory only. We solve the problem for three types of directed planar geometric networks: Eulerian (in which every vertex has the same number of incoming and outgoing edges), Outerplanar in which a single face contains all vertices of the network, and Strongly Face Connected, a new class of geometric networks that we define in the article, consisting of several faces, each face being a strongly connected outerplanar graph. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 7–15 2006

Summary form only given. The problem of traversal of planar subdivisions or other graph-like structures without using mark bits is central to many real-world applications. The first such algorithms were able to traverse triangulated subdivisions. Later these algorithms were extended to traverse vertices of an arrangement or a convex polytope. The research progress culminated in an algorithm that can traverse any planar subdivision. We extend the notion of planar subdivision to quasiplanar subdivision in which we allow many edges to cross each other. We describe an algorithm to traverse any quasiplanar subdivision that satisfies a simple requirement. The worst case running time of our algorithm is O(|E| log |E|), which matches the running time of the traversal algorithm for planar subdivisions.

We study virtual path layouts in a very popular type of fast interconnection networks, namely asynchronous transfer mode (ATM) networks. One of the main problems in such networks is to construct path layouts that minimize the hop-number (i.e., the number of virtual paths between any two nodes) as a function of the edge congestion c (i.e., the number of virtual paths going through a link). In this paper we construct for any n vertex network H and any c a virtual path layout with hop-number $O(\frac{diam(H)\log\Delta}{\log c})$, where diam(H) is the diameter of the network H and $\Delta$ is its maximum degree. Involving a general lower bound from [E. Kranakis, D. Krizanc, and A. Pelc, Seventh IEEE Symposium on Parallel and Distributed Processing, IEEE Computer Society, 1995, pp. 662--668], we see that these hop-numbers are optimal for bounded degree networks with the diameter O(log n) for any congestion c. In the case of unbounded degree networks (with the diameter O(log n)) these hop-numbers are optimal for any $c\geq\Delta$. For instance, this gives optimal hop-numbers for hypercube related networks. Moreover, we improve known results for paths and meshes and prove optimal hop-numbers for hypercubes.