Speaker
Iztok Peterin
(FEECS, University of Maribor, Slovenia and IMFM, Ljubljana, Slovenia)
Description
A walk $W$ between two non-adjacent vertices in a graph $G$ is
called tolled if the first vertex of $W$ is among vertices from $W$
adjacent only to the second vertex of $W$, and the last vertex of
$W$ is among vertices from $W$ adjacent only to the second-last
vertex of $W$. In the resulting interval convexity, a set $S\subset
V(G)$ is toll convex if for any two non-adjacent vertices $x,y\in S$
any vertex in a tolled walk between $x$ and $y$ is also in $S$.
We present that a graph is a convex geometry (i.e.
satisfies the Minkowski-Krein-Milman property stating that any
convex subset is the convex hull of its extreme vertices) with
respect to toll convexity if and only if it is an interval graph.
Furthermore, bounds for some well-known types of invariants are presented with respect to toll convexity, and toll convex sets in three standard graph products will be completely described.
Primary authors
Aleksandra Tepeh
(FEECS, University of Maribor, Slovenia)
Boštjan Brešar
(FNM, University of Maribor, Slovenia and IMFM, Ljubljana, Slovenia)
Iztok Peterin
(FEECS, University of Maribor, Slovenia and IMFM, Ljubljana, Slovenia)
Liliana Alc\'on
(Department of Mathematics, National University of La Plata, Argentina)
Marisa Gutierrez
(Department of Mathematics, National University of La Plata, CONICET, Argentina)
Tadeja Kraner Šumenjak
(FKBV, University of Maribor, Slovenia and IMFM, Ljubljana, Slovenia)
Tanja Gologranc
(IMFM, Ljubljana, Slovenia)
