CanaDAM 2021
En ligne, 25 - 28 mai 2021


NATALIE BEHAGUE, Ryerson University
The Cerny Conjecture and Synchronizing Times for k-sets in Automata  [PDF]

An automaton consists of a finite set of states and a collection of functions from the set of states to itself. An automaton is \emph{synchronizing} if there is a word (that is, a sequence of functions) that maps all states onto the same state. The \v{C}ern\'{y} conjecture is a famous open problem on the length of the shortest such word. We consider the closely related question of determining the minimum length of a word mapping $k$ states onto a single state.

For synchronizing automata, we have improved the upper bound on the minimum length of a word that sends some triple to a single state from $0.5n^2$ to $\approx 0.19n^2$. I will discuss this result and some related results, including a generalization of this approach this to an improved bound on the length of a synchronizing word for $4$ states and $5$ states.

This is joint work with Robert Johnson.

KATARÍNA ČEKANOVÁ, Pavol Jozef Šafárik University, Košice, Slovakia
Types of edges in embedded graphs with minimum degree 2  [PDF]

The weight $w(e)$ of an edge $e$ is the degree-sum of its end-vertices. An edge $e = uv$ is of type $(i, j)$ if $deg(u) \leq i$ and $deg(v) \leq j$. Kotzig proved that every 3-connected plane graph contains an edge of weight at most 13. Ivančo described bounds for weights of edges in the class of graphs embeddable on the orientable surfaces with higher genus. Jendroľ and Tuhársky investigated the weight of edges in the class of graphs embeddable on the nonorientable surfaces with higher genus. Later Jendroľ, Tuhársky and Voss described exact types of edges in large embedded maps with minimum degree 3.

In the talk we describe types of edges in connected embedded graphs with minimum degree at least 2, minimum face size at least 3 and sufficiently large number of vertices. We will also discuss the quality of our results.

SANTIAGO GUZMÁN PRO, Facultad de Ciencias, UNAM
Hereditary properties and forbidden orientations  [PDF]

Several graph properties are characterized as the class of graphs that admit an orientation avoiding finitely many oriented structures. For instance, if $F_k$ is the set of homomorphic images of the directed path on $k+1$-vertices, then a graph is $k$-colourable if and only if it admits an orientation with no induced oriented graph in $F_k$. There are two basic problems regarding this kind of characterizations: 1) given a finite set of oriented graphs, $F$, characterize the class of graphs that admit an $F$-free orientation, and 2) given a graph property, $\mathcal{P}$, determine if there a finite set of oriented graphs $F$ such that a graph belongs to $\mathcal{P}$ if and only if it admits an $F$-free orientation. We begin by addressing the first problem when $F$ is a set of oriented graphs on three vertices, and we conclude by exhibiting necessary conditions upon certain graph properties to admit such characterization.

YING YING (FAY) YE, University of Victoria
Chordality of locally semicomplete and weakly quasi-transitive digraphs  [PDF]

Chordal graphs are important in the structural and algorithmic graph theory. A digraph analogue of Chordal graphs was introduced by Haskin and Rose in 1973 but has not been studied until recently when a characterization of semicomplete chordal digraphs was found by Meister and Telle.

Locally semicomplete digraphs, quasi-transitive digraphs and extended semicomplete digraphs are the most popular generalizations of semicomplete digraphs. We extend the forbidden subdigraph characterization to Locally semicomplete chordal digraphs. We introduce weakly quasi-transitive digraphs, which contains qu- asitransitive digraphs, symmetric digraphs, and extended semicomplete digraphs, but is incomparable to locally semicomplete digraphs. We show that weakly quasi- transitive digraphs can be recursively constructed by substitutions from transitive oriented graphs, semicomplete digraphs, and symmetric digraphs. This recursive con- struction demonstrates the naturalness of the new digraph class. As a by-product, we prove that semicomplete chordal digraphs and weakly quasi-transitive chordal digraphs have the same forbidden subdigraphs.