Univerza na Primorskem Fakulteta za matematiko, naravoslovje in informacijske tehnologije
-->
SI | EN

Raziskovalni matematični seminar - Arhiv

2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010
1 2 3 4 5 6 7 8 9 10 11 12
Datum in ura / Date and time: 18.12.23
(15:00 -- 16:00)
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Safet Penjić (University of Primorska, Slovenia)
Naslov / Title: On combinatorial structure and algebraic characterizations of distance-regular digraphs
Vsebina / Abstract:

Let \G=\G(A) denote a simple strongly connected digraph with vertex set X, diameter D, and let \{A_0,A:=A_1,A_2,\ldots,A_D\} denote the set of distance-i matrices of \G. Let \{R_i\}_{i=0}^D denotes a partition of X\times X, where R_i=\{(x,y)\in X\times X\mid (A_i)_{xy}=1\} (0\le i\le D). The digraph \G is distance-regular if and only if (X,\{R_i\}_{i=0}^D) is a commutative association scheme. In this paper, we describe the combinatorial structure of \G in the sense of equitable partition and from it we derive several algebraic characterizations of such a graph.

Among else, we prove that the following (i)--(iii) are equivalent.
(i) \G is a distance-regular digraph.
(ii) \G is regular, has spectrally maximum diameter (D = d) and both matrices A^\top and the distance-D matrix A_D are polynomial in A.
(iii) (X,\{R_{\ii}\}_{\ii\in\Delta}) is a commutative D-class association scheme, where \Delta=\{(\partial(x,y),\partial(y,x))\mid x,y\in X\}, and for any \ii\in\Delta, R_{\ii} denote the set of ordered pairs (x,y)\in X\times X such that (\partial(x,y),\partial(y,x))=\ii (here \partial(x,y) denote the distance from vertex x to vertex y).

This is work in progress (it is joint work with Giusy Monzillo).

 

We look forward to seeing you there!


Datum in ura / Date and time: 11.12.23
(15:00 -- 16:00)
Predavalnica / Location: Famnit MP1
Predavatelj / Lecturer: Jean-Florent Raymond, CNRS, LIMOS, France
Naslov / Title: Induced paths in sparse graphs
Vsebina / Abstract:

Every induced path is a path, but the converse is not true. However in some classes of graphs (such as, for instance, planar graphs), the existence of a large path implies the existence of a long induced path. In 1982 Galvin, Rival, and Sands proved that such a statement holds in the general setting of graphs excluding a fixed biclique as subgraph. However in several cases their bound can be substantially improved.

In this talk I will present recent results on this topic in several sparse graph classes: graphs of bounded pathwidth, treewidth, degeneracy, and in topological-minor closed graph classes. 

This is joint work with Claire Hilaire and Oscar Defrain.

 

We look forward to seeing you there!