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č
Dodaj predavanje
(potrebno se je prijaviti)