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.