Seminár z algebraickej teórie grafov - James Tuite (11.12.2020)

v piatok 11.12.2020 o 13:00 hod. online formou

09. 12. 2020 22.45 hod.
Od: Martin Mačaj

Prednášajúci: James Tuite (Open University, UK)

Názov: Mixed graphs with order close to the Moore bound

Termín: 11.12.2020, 13:00 hod., MS Teams (AGT in Bratislava teamscheduled meeting)

The degree/girth problem asks for the smallest possible order of a $d$-regular graph with girth $\geq g$. Smallest possible graphs with given degree and girth are called \textit{cages}. This famous problem is one of the central topics of extremal graph theory; a survey can be found in [1]. A graph $G$ is \textit{$k$-geodetic} if for any two (not necessarily distinct) vertices $u, v \in V(G)$ there is at most one non-backtracking walk of length $\leq k$ from $u$ to $v$. It is easily seen that $G$ has girth $\geq 2k+1$ iff it is $k$-geodetic.

In this talk we will discuss a generalisation of the degree/girth problem for mixed and directed networks called the degree/geodecity problem: what is the smallest possible order of a $k$-geodetic directed or mixed graph with given degree parameters? We present new upper and lower bounds for the problem, together with some constructions of cages.

This is joint work with Grahame Erskine.

[1] Exoo, Geoffrey, and Jajcay, Robert. Dynamic cage survey, Electronic Journal of Combinatorics (2012): DS16-July. 


Due to recent restrictions imposed on us in response to the worsening of the situation with Covid infections in Slovakia, we will switch to distance mode. You will receive an MS Teams link over which you will be able to follow the presentation, ask questions, comment, and possibly even offer some solutions. While it is not better than being personally in the lecture room, it is not a terrible way to keep in touch either. Let us hope that we will soon be able to attend the meetings in person.