Raziskovalni matematični seminar - Arhiv

A graph G of even order is k-extendable if it has at least 2k+2 vertices, contains a matching of size k, and if every k-matching is contained in a perfect matching of G. In the talk we will discuss k-extendability of Cartesian product graphs and lexicographic product graphs.

This is a joint work with Cemil Dibek, Tinaz Ekim, Didem Gözüpek, Štefko Miklavič and Martin Milanič.

Everyone is warmly welcomed and encouraged to attend.

The Terwilliger algebra $T$ has been extensively studied in the context of distance-regular graphs, which have only a few irreducible $T$-modules (up to isomorphism) of a specific endpoint, all of which are thin (with respect to a certain base vertex). This talk aims to extend these results to irreducible $T$-modules with endpoint 0 of certain (not necessarily distance-regular) graphs, and shed some new light on their combinatorial properties. We examine which vertices $x$ of a finite, simple, and connected graph $\Gamma$ admit a Terwilliger algebra $T=T(x)$ with an irreducible $T$-module with endpoint $0$, which is thin. We give a purely combinatorial characterization to this algebraic property, which involves the number of certain walks in $\Gamma$ of a specific shape.

Scheduled Zoom meeting.
Join Zoom Meeting
https://upr-si.zoom.us/j/82792872242?pwd=Ym9VMVJUZHFCUC9BVWs3L1d1Mnh0UT09

Meeting ID: 827 9287 2242
Passcode: 899629

Excluding a graph (or a family of graphs) under a fixed containment relation can yield graph classes with very particular properties. Such properties can often be exploited for the design of efficient algorithms on the resulting graph classes. In this talk we survey several such structural parametrizations for the case of the Maximum Independent Set Problem, present new developments and open problems.

Everyone is welcome and encouraged to attend.