# Seminar IMFM in FNM v Mariboru iz diskretne matematike

Vodji seminarja: B. Brešar in S. Klavžar

Predavanja potekajo ob ponedeljkih ob **15:15 **v seminarski sobi P1 (Gosposvetska cesta 84, v 4. nadstropju).

### Bodoča predavanja

5.6.2017

A formal approach to operations on polyhedra

Predavatelj:
Gunnar Brinkmann (Ghent University, Belgija)

Abstract: Local operations on polyhedra that preserve the symmetries of the polyhedron have a long history. If you e.g. consider the Archimedean solids, already their names -- e.g. truncated cube or snub dodecahedron -- say how they were obtained: by applying an operation to a Platonic solid. Nevertheless it is not quite clear whether the names date back to Archimedes or were introduced by Keppler, who rediscovered the Archimedean solids. When asked what a "local symmetry preserving operation" is, a typical answer would not be a definition, but "for example truncation". Without a proper definition properties of the class of such operations cannot be studied of course. In this talk we will describe approaches of Goldberg, Caspar, Klug and Coxeter
to decorate polyhedra, show that the famous Goldberg/Coxeter operation was in fact first proposed by Caspar and Klug, show that the often cited paper by Goldberg has an -- obvious -- error and finally use the (corrected) approach by Goldberg for a formal approach to local operations on polyhedra that preserve symmetries.

5.6.2017

Well-covered Cartesian products

Predavateljica:
Kirsti Wash (Trinity College, Harford, ZDA)

Abstract: A graph is called well-covered if all maximal independent sets have the same cardinality. Hartnell and Rall showed that if $G$ and $H$ are graphs such that $G\Box H$ is well-covered, then at least one of $G$ or $H$ is well-covered. One may then ask whether we can characterize those graphs $H$ such that $G\Box H$ is well-covered. We will show that for any connected graph $G$ of girth at least 5 and minimum degree at least 2, $G\Box K_2$ is well-covered if and only if $G \cong C_5$. We also show that for any two connected graphs $G$ and $H$, both with girth at least 5, $G\Box H$ is well-covered if and only if $G\Box H \in \{K_2 \Box K_2, K_2 \Box C_5\}$.

### Minula predavanja

29.5.2017

Graph-like Continua: Characterizations and Eulerian Loops

Predavatelj:
Paul Gartside (University of Pittsburgh, ZDA)

Abstract: Locally finite graphs can be compactified, to form the Freudenthal
compactification, by adding their ends. This topological setting provides what
appears to be the ‘right’ framework for studying locally finite graphs. Indeed,
many classical theorems from finite graph theory that involve paths or
cycles have been shown to generalize to locally finite, infinite
graphs in this topological
setting, while failing to extend in a purely graph theoretic context.
More recently, compact
graph-like spaces were introduced by Thomassen and Vella, as a natural
class encompassing graphs, and their Freudenthal compactifications.
We present various characterizations of graph-like continua and
explore when they are Eulerian.

22.5.2017

Marjetične kocke

Predavatelj:
Sandi Klavžar

15.5.2017

Algoritmični vidiki konveksne dominacije

Predavateljica:
Tanja Gologranc

8.5.2017

The 3-smooth sequence

Predavatelj:
Andreas M. Hinz

24.4.2017

Some properties of finite fields and their applications to generalizations of strongly regular graphs

Predavatelj:
Vladislav V. Kabanov (Russian Academy of sciences, Yekaterinburg, Rusija)

10.4.2017

Some bounds on the generalised total chromatic number of degenerate graphs

Predavatelj:
Gabriel Semanišin (PJŠ University in Košice, Slovaška)

The total generalised (P,Q)-colourings are colourings of the vertices and of the edges of graphs satisfying the following conditions:

• each set of vertices of the graph which receive the same colour induces a graph possessing prescribed property P,

• each set of edges of the graph which receive the same colour induces a graph possessing prescribed property Q, and

•incident elements receive different colours.

In our contribution we shall deal with a specific situation when the properties P and Q are “to be k-degenerate”. Bounds for the least number of colours with which this can be done for all k-degenerate graphs are obtained. Moreover we shall discuss some applications for a communication is Wireless Sensor Networks.

.

References:

• F. Galčík, G. Semanišin, Centralized broadcasting in radio networks with k-degenerate reachability graphs, in: ITAT 2006 Information Technologies – Applications and Theory, Bystrá dolina, Slovakia, 2006, pp. 41–46.

• I. Broere, G. Semanišin, Some bounds on the generalised total chromatic number of degenerate graphs, Inform. Proc. Letters 122 (2017) 30–33, http://dx.doi.org/10.1016/j.ipl.2017.02.008

10.4.2017

k-path partition and k-path vertex cover

Predavatelj:
Rastislav Krivoš-Belluš (PJŠ University in Košice, Slovaška)

Motivated by the problem of ensuring data integrity of communication in wireless sensor networks using the k-generalised Canvas scheme Brešar et al. introduced the minimum k-path vertex cover problem (MkPVCP), a generalisation of the minimum vertex cover problem. Although it is a new problem in graph theory, many people have spent a lot of effort in studying it. The problem is known to be NP-hard.

In this presentation, we present several algorithms solving MkPVCP, also for the weighted version of the problem. Afterwards we will focus on the relation of the MkPVCP with the minimum k-path partition problem. Recently we have obtained new bounds for their invariants and a new sufficient condition for NP-hardness of the MkPVCP in terms of forbidden subgraphs.

.

References:
Ch. Brause, R. Krivoš-Belluš, On a relation between k-path partition and k-path vertex cover, In press in Discrete Appl. Mathematics, http://dx.doi.org/10.1016/j.dam.2017.01.013

3.4.2017

Minorji v delnih kockah

Predavatelj:
Tilen Marc

27.3.2017

Finite sets and the pigeonhole principle

Predavatelj:
Andreas M. Hinz

20.3.2017

The Star Tower of Hanoi

Predavatelj:
Andreas M. Hinz

13.3.2017

Grundyjeva celotna dominantna števila: realizacija in algoritmični vidiki

Predavatelj:
Tim Kos

6.3.2017

Distinguishing trees and subcubic graphs

Predavatelj:
Wilfried Imrich

Abstract: Thomas Tucker's infinite motion conjecture asserts that the vertices of every connected, locally finite graph G can be colored with 2 colors such that the identity automorphism is the only automorphism that respects the coloring under the condition that every automorphism moves infinitely many vertices. We say G is 2-distinguishable if it has infinite motion.

The conjecture is true for many classes of graphs, but it is not known whether it holds for graphs with given maximum degree k, unless k=3.
Such graphs are called subcubic. However, there is evidence that infinite motion is not needed for subcubic graphs and that one can always find a 2-coloring that fixes all vertices with the exception of at most two pairs of interchangeable vertices. We show that this is true for trees, subcubic graphs without small cycles and vertex transitive cubic graphs.

In particular, we show that every subcubic infinite tree is 2-distinguishable and that every finite subcubic tree has a 2-coloring, which fixes all vertices, with the possible exception of two vertices of degree 1 with a common neighbor. We also show that the only vertex or edge-transitive finite or infinite subcubic graphs are the K_4, the K_{3,3} or the cube.

For finite or infinite trees of maximum valence k we show that there is a 2-coloring that fixes all vertices that have no endvertex within distance log_2 k +1 .

Acknowledgement: This joint work with Thomas Lachmann and Gundelinde Wiegel (vertex transitive graphs), Svenja Hüning, Judith Kloas and Hannah Schreiber (trees) and Thomas Tucker.

Speaker: Wilfried Imrich and possibly one of the co-authors.

27.2.2017

(s,t)-sproščene L(2,1) označitve grafov

Predavatelj:
Aleksander Vesel

20.2.2017

Varne množice v leksikografskem produktu

Predavatelj:
Marko Jakovac

16.1.2017

Konstrukcije prekrižno-kritičnih grafov s predpisanimi lastnostmi II

Predavateljica:
Mojca Bračič

9.1.2017

Konstrukcije prekrižno-kritičnih grafov s predpisanimi lastnostmi I

Predavateljica:
Mojca Bračič